---

0942. 增减字符串匹配

• 标签：贪心、数组、双指针、字符串
• 难度：简单

题目链接

• 0942. 增减字符串匹配 - 力扣

题目大意

描述：

由范围 $[0, n]$ 内所有整数组成的 $n + 1$ 个整数的排列序列可以表示为长度为 $n$ 的字符串 $s$，其中:

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

给定一个字符串 $s$。

要求：

重构排列 $perm$ 并返回它。如果有多个有效排列 $perm$，则返回其中任何一个。

说明：

• $1 \le s.length \le 10^{5}$。
• $s$ 只包含字符 "I" 或 "D"。

示例：

• 示例 1：

输入：s = "IDID"
输出：[0,4,1,3,2]

• 示例 2：

输入：s = "III"
输出：[0,1,2,3]

解题思路

思路 1：贪心算法

思路

这道题要求根据字符串 $s$ 构造一个排列 $perm$，使得相邻元素的大小关系符合 $s$ 中的 I（递增）和 D（递减）。

我们可以使用贪心策略：

• 维护两个指针 $low$ 和 $high$，分别指向当前可用的最小值和最大值。
• 遍历字符串 $s$：
  • 如果遇到 I，说明下一个数要比当前数大，我们选择当前最小的可用数 $low$，然后 $low$ 加 $1$。
  • 如果遇到 D，说明下一个数要比当前数小，我们选择当前最大的可用数 $high$，然后 $high$ 减 $1$。
• 最后还剩一个数，此时 $low$ 和 $high$ 相等，将其加入结果。

代码

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        n = len(s)
        low, high = 0, n  # 初始化最小值和最大值
        res = []
        
        # 遍历字符串 s
        for ch in s:
            if ch == 'I':
                # 递增，选择当前最小值
                res.append(low)
                low += 1
            else:
                # 递减，选择当前最大值
                res.append(high)
                high -= 1
        
        # 最后剩下一个数，low 和 high 相等
        res.append(low)
        
        return res

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。只需要遍历一次字符串。
• 空间复杂度：$O(1)$，不考虑结果数组的空间，只使用了常数个额外变量。