題目資訊

• 題目編號: 2375
• 題目連結: Construct Smallest Number From DI String
• 主題: String, Backtracking, Stack, Greedy

題目敘述

您有一個0索引的字串 pattern，長度為 $n$，由表示遞增的字元 'I' 和表示遞減的字元 'D' 組成。

利用以下條件創建了一個長度為 $n + 1$ 的0索引字串 num：

• num 由數字 '1' 到 '9' 組成，其中每個數字最多使用一次。
• 如果 pattern[i] == 'I'，那麼 $num[i] < num[i + 1]$。
• 如果 pattern[i] == 'D'，那麼 $num[i] > num[i + 1]$。

返回字典序最小的 num ，使其滿足這些條件。

範例 1:

輸入: pattern = “IIIDIDDD”
輸出: “123549876”
解釋:
在索引 0, 1, 2 和 4，我們必須使 $num[i] < num[i+1]$。
在索引 3, 5, 6 和 7，我們必須使 $num[i] > num[i+1]$。
一些可能的 num 值有 “245639871”, “135749862”, 和 “123849765”。
可以證明 “123549876” 是滿足這些條件的最小可能 num。
注意 “123414321” 是不可能的，因為數字 ‘1’ 被多次使用。

範例 2:

輸入: pattern = “DDD”
輸出: “4321”
解釋:
一些可能的 num 值有 “9876”, “7321”, 和 “8742”。
可以證明 “4321” 是滿足這些條件的最小可能 num。

約束條件:

• $1 \leq \text{pattern.length} \leq 8$
• pattern 僅包含字母 'I' 和 'D'。

直覺

這個問題主要涉及到構建一個符合給定遞增和遞減關係模式的數字字符串。需要生成字典序最小的字符串，這提示我們應保持有序的序列，其中遞增的子序列條件（‘I’）可以通過順序使用最小的未使用數字來自然滿足。相反，對於遞減的子序列條件（‘D’），較大的數字應排在較小的數字之前。為了有效地跟踪順序，同時保證字典序最小的順序，利用堆疊數據結構可以是有利的。這種方法利用堆疊的「後進先出」屬性，使我們可以按需逆轉子序列。

解法

該方法涉及遍歷給定模式中的每一個字符。我們必須生成一個遵循模式規則的數字序列：

1. 初始化結構：創建一個空字符串result來存儲最終數字，並創建一個堆疊st以管理數字順序。

2. 遍歷模式：

   • 對於從索引 i 到模式的長度（包括一個附加的步驟以處理最後一個字符，由於 result 的長度是 $n + 1$）的每一個索引，將下一個可用的數字（i + 1）推入堆疊。
   • 檢查兩種情況：
     • 當我們到達模式的結尾。
     • 當當前字符 pattern[i] 是 ‘I’。

3. 構建結果：

   • 當堆疊非空且滿足上述任一條件時，從堆疊中彈出頂部元素，並將其附加到result中。此操作用於在遇到 ‘I’ 時或我們已處理完模式中的所有字符時，強制得到字典序最小的順序。

4. 完成：

   • 返回 result，其現在應包含滿足給定模式約束的最小可能數字。

這種方法有效利用堆疊來確保遞減段以逆序解決，因此自然能夠滿足模式的需求，同時保持字典序的優先順序。

程式碼

C++

class Solution {
public:
    string smallestNumber(string pattern) {
        string result = "";  // 用來儲存最終結果的變數
        stack<int> st;       // 用於生成數字的堆疊

        // 遍歷pattern，並處理比pattern長度多一位的數字
        for(int i = 0; i <= pattern.size(); i++) {
            // 將下一個遞增的數字推入堆疊
            st.push(i + 1);

            // 如果到達pattern的結尾或遇到'I'，則構建按字典序最小的數字
            while(!st.empty() && (i == pattern.size() || pattern[i] == 'I')) {
                // 從堆疊中彈出並附加到結果中以確保序列條件
                result += '0' + st.top();
                st.pop();
            }
        }

        return result;  // 返回符合pattern的最小數字
    }
};

Python

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        result = ""  # 用於存儲最終結果的變數
        st = []  # 用於輔助生成數字的堆疊

        # 遍歷pattern，處理比pattern長度多一位的數字
        for i in range(len(pattern) + 1):
            # 將下一個遞增的數字推入堆疊
            st.append(i + 1)

            # 如果到達pattern的結尾或遇到'I'，構造字典序最小的數字
            while st and (i == len(pattern) or pattern[i] == 'I'):
                # 從堆疊中彈出並附加到結果，以確保序列條件
                result += str(st.pop())
        
        return result  # 返回符合模式的最小數字

複雜度分析

• 時間複雜度: $O(n)$
  演算法遍歷模式中的每個字符，模式長度為 $n$。對於每個字符，演算法可能將一個元素推入堆疊。然後，在某些條件下（如模式結束或遇到 ‘I’），會從堆疊中彈出所有元素，每個字符最多發生一次。因此，每個元素（推入和彈出）都被處理一次，這導致時間複雜度相對於模式長度是線性的，即 $O(n)$。

• 空間複雜度: $O(n)$
  空間複雜度由演算法中使用的輔助堆疊決定。在最壞的情況下，當整個模式由 ‘D’ 組成時，所有可能的數字（最多為 $n+1$ 個）在彈出之前都被推入堆疊。因此，堆疊最多可以容納 $n+1$ 個元素，這導致空間複雜度為 $O(n)$。