942. DI String Match 增减字符串匹配

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客： http://fuxuemingzhu.cn/
• 关键词：力扣，LeetCode，题解，解析，942，Python, C++, Java, 题意

---

@TOC

题目地址：https://leetcode.cn/problems/di-string-match/

题目描述

由范围 [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：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 10^5
• s 只包含字符 "I" 或 "D"

题目大意

给出一个字符串只包含 I和 D，求数组 $[0～N]$的一个排列，使得：

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

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

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

这个字符串的含义是让我们找到一个 增减增减的数组。数组的长度是 s的长度 $+1$，即 $5$；数组中的数字必须是 $[0,1,2,3,4]$这 $5$ 个数字，必须不重复、不遗漏。

直白点就是问我们，怎么把 $[0,1,2,3,4]$排列成 增减增减的形状。

所以题目，给出了一种答案：$[0,4,1,3,2]$这样。

有没有其他答案呢？也是有的，比如 $[1,4,0,3,2]$也是 增减增减的形状。

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

解题方法

贪心算法

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

我们尝试进行分析，仍以s = "IDID"为例，即要把$[0,1,2,3,4]$重新排列 ：

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

所以对于s = "IDID"而言，待重新排序的数组是 $[0,1,2,3,4]$。我们对 s进行遍历：

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

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

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

Python 代码如下：

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 

C++ 代码如下：

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;
    }
};

Java 代码如下：

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. 这种找规律题目，不妨按照题目给出的示例，自己去琢磨一下。

日期

2018 年 11 月 18 日 —— 出去玩了一天，腿都要废了 2022 年 5 月 9 日 —— 在力扣恢复日更题解，目前感觉良好