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

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

转载作者：大佬之路更新时间：2024-01-31 14:16:02

关键词：力扣，LeetCode，题解，解析，942，Python, C++, Java, 题意

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

题目描述

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18