942. 增减字符串匹配 - 力扣

1. 题目

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

2. 示例

3. 分析

这道题目的意思就是如果字符是 I ，则当前元素需小于后一个元素；若为 D ，则当前元素需大于后一个元素：

以下摘抄自 官方题解 ：

考虑 perm[0] (返回数组) 的值，根据题意：

• 如果 s[0] = 'I'，那么令 perm[0] = 0，则无论 perm[1] 为何值都满足 perm[0] < perm[1]；
• 如果 s[0] = 'D'，那么令 perm[0] = n，则无论 perm[1] 为何值都满足 perm[0] > perm[1]；

确定好 perm[0] 后，剩余的 n−1 个字符和 n 个待确定的数就变成了一个和原问题相同，但规模为 n−1 的问题。因此我们可以继续按照上述方法确定 perm[1]：如果 s[1] = 'I'，那么令 perm[1] 为剩余数字中的最小数；如果 s[1] = 'D'，那么令 perm[1] 为剩余数字中的最大数。如此循环直至剩下一个数，填入 perm[n] 中。即 I 就放剩余数字中的最小数，D 就放剩余数字中的最大数。

我们可以定义两个指针，表示剩余待确定数字中的最小和最大值：

class Solution {
public:vector<int> diStringMatch(string s) {int n = s.size();vector<int> res(n+1);int min = 0, max = n;for(int i = 0; i < n; i++){if(s[i] == 'I') {res[i] = min;min++;}               else {res[i] = max;max--;}}res[n] = max; // 还剩最后一个数，此时 min == maxreturn res;}
};