leetcode 899. 有序队列-蒲公英云

leetcode 899. 有序队列

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回在应用上述步骤的任意数量的移动后，字典上最小的字符串。

示例 1：

输入：s = “cba”, k = 1
输出：“acb”
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例 2：

输入：s = “baaca”, k = 3
输出：“aaabc”
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

提示：

1 <= k <= S.length <= 1000
s 只由小写字母组成。

思路：

当k==1时，将原字符串看成一个环，从开头到结尾每次都将第一个字符放在末尾，保存这些字符中的字典序最小的情况，直接模拟。

当k>=2时，经过有限次的操作，一定可以变成升序，因为我们每次在前k个中都可以选择最大的那个放在最后，这样实际操作起来很麻烦，但和sort排好序的结果是一样的，所以直接sort返回即可。

class Solution {
public:
    string orderlyQueue(string s, int k) {
        if(k>1){
            sort(s.begin(),s.end());
            return s;
        }
        string ans=s;
        for(int i=0;i<s.size();++i){
            s=string{
    s.begin()+1,s.end()}+s[0];
            ans=min(ans,s);
        }
        return ans;
    }
};