484.寻找排列

484.寻找排列

题目大意:给一串DDII…D代表下降趋势,I代表上升.根据这一串DDII的序列构建出一个整数vector,且若有多个vector符合要求,返回字典序最小的.

解题思路:根据讨论的思路,首先构建出完全增序(IIII…)的序列1,2,3,4,…n,然后找序列中所有的D,将对应位置的序列反转即可.

class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.length();
        if (!n) return vector<int>();
        vector<int> res(n+1);
        for (int i = 0; i < n+1; i++) res[i] = i+1;  //初始增序序列
        //一次遍历字符串
        for (int i = 0; i < n; i++) {
            int start = 0, end = 0;
            if (s[i] == 'D') {  //找'D'
                start = i;  //记录起始位置
                while(s[i+1] == 'D') i++;
                end = i;  //记录结束位置
                reverse(res.begin()+start, res.begin()+end+2);  //将对应位置的段落整体反转
            }           
        }
        return res;
    }
};