LeetCode刷题实战484：寻找排列

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 寻找排列，我们先来看题面：

https://leetcode-cn.com/problems/find-permutation/

By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signaturewas constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.

On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, … n] could refer to the given secret signature in the input.

现在给定一个只由字符 ‘D’ 和 ‘I’ 组成的秘密签名。’D’ 表示两个数字间的递减关系，’I’ 表示两个数字间的递增关系。并且秘密签名是由一个特定的整数数组生成的，该数组唯一地包含 1 到 n 中所有不同的数字（秘密签名的长度加 1 等于 n）。例如，秘密签名 “DI” 可以由数组 [2,1,3] 或 [3,1,2] 生成，但是不能由数组 [3,2,4] 或 [2,1,3,4] 生成，因为它们都不是合法的能代表 “DI” 秘密签名的特定串。

现在你的任务是找到具有最小字典序的 [1, 2, … n] 的排列，使其能代表输入的秘密签名。

示例

示例 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。

解题

https://blog.csdn.net/weixin_44171872/article/details/108930534

主要思路：

（1）使用贪心的思想；

（2）想将数组进行从1到n的初始化，然后遍历给出的字符串，当字符串的值是‘I’时，跳过，当字符串的值是‘D’时，使用循环找出连续的‘D’的范围，然后将该范围对应的数组中的元素进行反序；

class Solution {
public:
    vector<int> findPermutation(string s) {
        vector<int> res(s.size()+1);//定义数组
        //对数组进行赋值
        for(int i=0;i<res.size();++i){
            res[i]=i+1;
        }
        int pos=0;
        //遍历字符串
        while(pos<s.size()){
            if(s[pos]=='I'){//因为数组已经是升序的
                ++pos;
                continue;
            }
            int cur_start=pos;//需要降序的起始位置
            //找出需要降序的终止位置
            while(pos<s.size()&&s[pos]=='D'){
                ++pos;
            }
            //将该范围内的数进行反序，实现降序
            reverse(res.begin()+cur_start,res.begin()+pos+1);
        }
        return res;
    }
};