题目

由范围 [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 ，则返回其中 任何一个 。

来源：力扣（LeetCode）

解答

题目人话翻译

给定一个长度为 n 的字符串，字符串只有两个字符 I 和 D。

再给你 0 - n 一共 n + 1 个整数，让你遵循以下规律把所有整数依次填到合适的位置，组成一个大小为 n + 1 的数组：

1. 遍历到字符 I 时，则下一个位置的数字比当前小；
2. 遍历到字符 D 时，则下一个位置的数字比当前大。

要求每个整数只用一次，且排列不唯一，返回任意满足条件的即可。

贪心解答

当分配整数时，遇到 I 就给当前分配余下整数中的最小值，反之遇到 D 则分配最大值。

代码如下：

class Solution {
public:
    vector<int> diStringMatch(string s) {
        vector<int> ret;
        int min_val = 0;
        int max_val = s.size();

        for (auto i: s) {
            if (i == 'I') {
                ret.push_back(min_val);
                min_val++;
            } else {
                ret.push_back(max_val);
                max_val--;
            }
        }
        ret.push_back(min_val); // min_val or max_val

        return ret;
    }
};