今日题目

https://leetcode.com/problems/construct-smallest-number-from-di-string/

思路

本题要求我们在一定约束条件下找出一个数字序列。

首先观察到序列长度 N 非常小，因此可以用 DFS 枚举所有可能的情况并得出结果。

另一种思路是使用栈。当序列递增时，构造合法序列的最优策略是依次填入当前最小可用数字。当序列递减时，由于我们仍然希望序列整体尽可能小，需要填入当前可用的最小数字，而该数字还必须大于后续位置的数字。因此，当前位置能填入的最小数字，等于当前下标加上后续连续 ‘D’ 的个数。 基于此，可以用一个栈暂存正在遍历的数字，每当遇到 ‘I’ 或到达序列末尾时，再将栈中元素逆序追加到结果数组中。

方法

对于解法一（DFS），只需枚举所有方案，返回第一个满足条件的结果即可。

对于解法二（栈），当遇到 ‘I’ 时，将 idx + 1 加入结果数组，然后将栈中所有元素逆序弹出追加到结果数组，再清空栈；当遇到 ‘D’ 时，将 idx + 1 压入栈中留待后续处理。

技巧

  • DFS：由于题目要求找最小的合法序列，所以第一个非 None 的结果就是答案。这意味着一旦找到合法结果就可以立即返回，无需继续搜索。

  • 栈：此处我特意在序列末尾追加了一个 ‘D’。 直觉上，序列的最后一个元素是整个序列中最大的数，要将其放入结果数组，需要执行一次 ‘D’ 操作。 这样一来，若原序列最后一个字符是 ‘I’，则可以直接将最大数追加到结果末尾，效果等同于一次 ‘D’ 操作——因为 ‘I’ 操作会清空栈，栈中只剩一个元素，正序或逆序追加结果相同。 若原序列最后一个字符是 ‘D’，则最大数应放在连续 ‘D’ 序列开始的位置，此时需要一次 ‘D’ 操作将其放到正确位置。 这个技巧让代码更加简洁优雅，但牺牲了可读性，实际使用中不建议采用。

复杂度

  • DFS 解法时间复杂度：$O(N!)$，N 为序列长度。

  • 栈解法时间复杂度：$O(N)$，N 为序列长度。

  • DFS 解法空间复杂度：$O(N)$，N 为序列长度。

  • 栈解法空间复杂度：$O(N)$，N 为序列长度。

代码

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        arr = []
        n = len(pattern) + 2
        def dfs(arr):
            if len(arr) == n - 1:
                return arr
            now = len(arr) - 1
            res = None
            if pattern[now] == 'I':
                for i in range(arr[now] + 1, n):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            else:
                for i in range(1, arr[now]):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            
            return res


        for i in range(1, n):
            ans = dfs([i])
            if ans is not None:
                return ''.join(map(str, ans))
                # return ans
        
        return None

image.png

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        arr = []
        n = len(pattern) + 2
        def dfs(arr):
            if len(arr) == n - 1:
                return arr
            now = len(arr) - 1
            res = None
            if pattern[now] == 'I':
                for i in range(arr[now] + 1, n):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            else:
                for i in range(1, arr[now]):
                    if i not in arr:
                        res = dfs(arr + [i])
                        if res is not None:
                            return res
            
            return res


        for i in range(1, n):
            ans = dfs([i])
            if ans is not None:
                return ''.join(map(str, ans))
                # return ans
        
        return None

image.png

更多解题思路，欢迎访问我的博客。