青海省教育厅门户网站首页品牌大全
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;}
};