---

0484. 寻找排列

• 标签：栈、贪心、数组、字符串
• 难度：中等

题目链接

• 0484. 寻找排列 - 力扣

题目大意

描述：

给定一个由 'I'（递增）和 'D'（递减）组成的字符串 $s$，长度为 $n$。

$s$ 描述了一个排列 $perm$（由 $1$ 到 $n$ 的整数组成）的相邻比较关系：

• 如果 $perm[i] < perm[i+1]$，则 $s[i] == 'I'$（递增）
• 如果 $perm[i] > perm[i+1]$，则 $s[i] == 'D'$（递减）

需要找到一个由 $1$ 到 $n+1$ 组成的排列，使得：

• 如果 $s[i] = 'I'$，则 $perm[i] < perm[i+1]$。
• 如果 $s[i] = 'D'$，则 $perm[i] > perm[i+1]$。

要求：

满足该 $s$ 条件的「字典序最小」的排列 $perm$。

说明：

• $1 \le s.length \le 10^5$。
• $s$ 只包含字符 'I' 和 'D'。

示例：

• 示例 1：

输入：s = "I"
输出：[1,2]
解释：[1,2] 是唯一满足条件的排列。

• 示例 2：

输入：s = "DI"
输出：[2,1,3]
解释：[2,1,3] 和 [3,1,2] 都满足条件，但 [2,1,3] 字典序更小。

解题思路

思路 1：栈 + 贪心

给定一个由 'I'（递增）和 'D'（递减）组成的字符串 $s$，需要找到字典序最小的排列，使得相邻元素满足递增或递减关系。

核心思路：

• 使用贪心策略：尽可能让前面的数字小。
• 遇到 'I' 时，应该让当前数字尽可能小。
• 遇到连续的 'D' 时，需要将这段数字按降序排列。

解题步骤：

1. 初始化结果数组，长度为 $n + 1$（$n$ 是字符串长度）。
2. 使用栈来处理连续的 'D'。
3. 遍历字符串，将数字 $1$ 到 $n + 1$ 依次处理：
   • 将当前数字压入栈。
   • 如果遇到 'I' 或到达末尾，将栈中所有数字弹出并加入结果。
   • 这样可以保证连续的 'D' 对应的数字是降序的。

思路 1：代码

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        n = len(s)
        result = []
        stack = []
        
        # 遍历 1 到 n+1
        for i in range(1, n + 2):
            stack.append(i)
            
            # 如果遇到 'I' 或到达末尾，弹出栈中所有元素
            if i == n + 1 or s[i - 1] == 'I':
                while stack:
                    result.append(stack.pop())
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度。每个数字最多入栈和出栈各一次。
• 空间复杂度：$O(n)$，栈的空间开销。