LeetCode 484. 寻找排列（找规律+贪心）

示例 1：
输入： "I"
输出： [1,2]
解释： [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串，
数字 1 和 2 构成递增关系。
 
示例 2：
输入： "DI"
输出： [2,1,3]
解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI"，
但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。
 
注：
输出字符串只会包含字符 'D' 和 'I'。
输入字符串的长度是一个正整数且不会超过 10,000。

class Solution {
public:
    vector<int> findPermutation(string s) {
    	int n = s.size(), idx, l = 0, r = 0;
    	vector<int> ans(n+1);
    	for(idx = 1; idx <= n+1; ++idx)
    		ans[idx-1] = idx;
    	while(r < n)
    	{
            
    		if(s[r] == 'I')
    		{
                if(l < r)
                {
                    reverse(ans, l, r);
                    l = r;
                }
                l++, r++;
            }
    		else//下降
    			r++;
    	}
        if(l < r)
            reverse(ans, l, r);
    	return ans;
    }
    void reverse(vector<int>& ans, int i, int j)
    {
    	while(i < j)
    		swap(ans[i++], ans[j--]);
    }
};