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 只由小写字母组成。

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/orderly-queue
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

题目要求每次可以拿出前k个字符中的一个放到最后。
显然当k=1时，我们只能每次将第一个字符放到最后，这种情况下我们只需找出每次将头元素放到尾部能得到的最小值就好了，由于c++的string支持直接比较大小，这样就很好实现了。
当k>1时我们就可以做到将整个字符串s重新排成任何想要的序列，这是怎么实现的呢？
由于我们每次可以从至少两个字符中选择一个放到末尾，所以就能做到交换两个字符的顺序，举个例子：

1.原序列为atsdfg，我们要交换sd的顺序就这样做
2.先把sd前面的字符按顺序放到末尾，变成sdfgat
3.然后先放d再放s变成fgatds
4.最后把剩下的字符依次放到末尾变成atdsfg，这样就实现了两个字符的交换
5.接下来类比冒泡排序不断将最大的字符放到末尾就能实现全部字符的升序排列了，所以直接sort(s.begin(),s.end())即可。

---

代码：

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