942. 增减字符串匹配

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

给出一个字符串只包含 I和 D，求数组 的一个排列，使得：

• 如果字符串的某个位置是 I，那么数组下一个数字是增加的；
• 如果字符串的某个位置是 D，那么数组下一个数字是减小的。

用下面的图帮助理解，我用了题目中的两个例子s = "IDID"和 "s = DDI"。

根据图，我再解释一下s = "IDID"这个例子。

这个字符串的含义是让我们找到一个 增减增减的数组。数组的长度是 s的长度 ，即 ；数组中的数字必须是 这 个数字，必须不重复、不遗漏。

直白点就是问我们，怎么把 排列成 增减增减的形状。

所以题目，给出了一种答案：这样。

有没有其他答案呢？也是有的，比如 也是 增减增减的形状。

题目也说了，只要是符合 s要求的任意一个排列，都是正确答案。所以上面两种排列都是对的。

解题方法

贪心算法

这个题其实有规律可循的，如果注意看题目给的例子，其实也是有规律的。

我们尝试进行分析，仍以s = "IDID"为例，即要把重新排列 ：

1. 假如 s当前的字符是 I，说明数组中的下一个数字比当前数字大；
   1. 假如我们把数组中的当前安排成 ，那就完犊子了，因为不存在比 更大的数字了。
   2. 所以我们当遇到 I的时候，我们最好的选择是当前能放的最小数字。这样，无论下一个数字放谁，都会比当前数字大。都能符合 I。
2. 假如 s当前的字符是 D，说明数组中的下一个数字比当前数字小；
   1. 假如我们把数组中的当前安排成 ，那就完犊子了，因为不存在比 更小的数字了。
   2. 所以我们当遇到 D的时候，我们最好的选择是当前能放的最大数字。这样，无论下一个数字放谁，都会比当前数字小。都能符合 D。

所以对于s = "IDID"而言，待重新排序的数组是 。我们对 s进行遍历：

1. s第一个的字符是 I，当前候选集是 $[0,1,2,3,4]$，我们选择最小值 （无论下一个数字放谁，都比 大，所以都是增加）；此时结果数组为 $[0]$；
2. s第二个的字符是 D，当前候选集是 $[1,2,3,4]$，我们选择最大值 （无论下一个数字放谁，都比 小，所以一定减小）；此时结果数组为 $[0, 4]$；
3. s第三个的字符是 I，当前候选集是 $[1,2,3]$，我们选择最大值 （ 无论下一个数字放谁，都比 大，所以都是增加）；此时结果数组为 $[0, 4, 1]$；
4. s第四个的字符是 D，当前候选集是 $[2,3]$，我们选择最大值 （无论下一个数字放谁，都比 小，所以一定减小）；此时结果数组为 $[0, 4, 1, 3]$；
5. s遍历完成，候选集还剩 $[2]$， 我们把最后这个数字放在结果数组中，结果数组为 $[0, 4, 1, 3, 2]$；

总之，就是一个贪心策略，遇到 I就选剩余候选集的最小值，遇到 D就选剩余候选集的最大值。

下面的代码中，为了保存当前的最小值和最大值，分别使用了两个变量 ni和 nd。

代码如下：

class Solution:
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        N = len(S)
        ni, nd = 0, N
        res = []
        for s in S:
            if s == "I":
                res.append(ni)
                ni += 1
            else:
                res.append(nd)
                nd -= 1
        res.append(ni)
        return res

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int ni = 0;
        int nd = s.size();
        vector<int> res;
        for (char c : s) {
            if (c == 'I') {
                res.push_back(ni);
                ni ++;
            } else {
                res.push_back(nd);
                nd --;
            }
        }
        res.push_back(ni);
        return res;
    }
};

class Solution {
    public int[] diStringMatch(String s) {
        int[] res = new int[s.length() + 1];
        int ni = 0;
        int nd = s.length();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'I') {
                res[i] = ni;
                ni ++;
            } else {
                res[i] = nd;
                nd --;
            }
        }
        res[s.length()] = ni;
        return res;
    }
}

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

  总结

1. 这种找规律题目，不妨按照题目给出的示例，自己去琢磨一下。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。