行业知识
【Leetcode】899. Orderly Queue（配数学证明）
题目地址：
https://leetcode.com/problems/orderly-queue/description/
（）给定一个长 n n n字符串 s s s，和一个正整数 k k k， k ≤ n k\le n k≤n。允许做若干次操作，每一次将 s s s的前 k k k个字母其中的一个移到最后。问这样操作能得到的字典序最小的字符串是什么。
如果 k = 1 k=1 k=1，那么其实就是求 s s s所有轮换的最小字典序，直接暴力枚举即可。如果 k > 1 k>1 k>1，我们可以证明任何对换都能由上面的操作得到。设下标从 1 1 1开始。例如交换 x x x和 y y y，设 s = s 1 + x + s 2 + y + s 3 s=s_1+x+s_2+y+s_3 s=s1+x+s2+y+s3，那么我们可以先将 s 1 s_1 s1移到后面去得 x + s 2 + y + s 3 + s 1 x+s_2+y+s_3+s_1 x+s2+y+s3+s1，接着移 s 2 s_2 s2得 x + y + s 3 + s 1 + s 2 x+y+s_3+s_1+s_2 x+y+s3+s1+s2，再移 x x x得 y + s 3 + s 1 + s 2 + x y+s_3+s_1+s_2+x y+s3+s1+s2+x，再移 s 3 + s 1 s_3+s_1 s3+s1得 y + s 2 + x + s 3 + s 1 y+s_2+x+s_3+s_1 y+s2+x+s3+s1，再移 y + s 2 + x + s 3 y+s_2+x+s_3 y+s2+x+s3得最终结果。所以本质上任意排列都能得到，所以直接排序就行了。代码如下：
class Solution { public: string orderlyQueue(string s, int k) { if (k > 1) { sort(s.begin(), s.end()); return s; } string res = s; for (int i = 1; i 当 k = 1 k=1 k=1的时候时间复杂度是 O ( n 2 ) O(n^2) O(n2)，否则时间 O ( n log n ) O(n\log n) O(nlogn)，空间 O ( 1 ) O(1) O(1)，空间 O ( 1 ) O(1) O(1)。
（）
