899. 有序队列

题目描述

给你一个字符串 s 和一个整数 k。

你可以选择字符串 s 的 前 k 个字母中的任意一个，并把它移动到字符串末尾。

请你返回在执行任意次操作后，可以得到的 字典序最小 的字符串。

示例 1

输入：s = "cba", k = 1
输出："acb"

示例 2

输入：s = "baaca", k = 3
输出："aaabc"

约束

• 1 <= k <= s.length <= 1000
• s 只由小写英文字母组成

核心思路

这题最关键的地方在于：

• k = 1 和 k > 1，本质上是 两种完全不同的情况

为什么这么说？

因为当 k = 1 时：

• 你每次只能选第 1 个字符
• 也就是只能把 最前面的字符 移到末尾
• 这等价于：不断对字符串做循环左移

而当 k > 1 时：

• 你前 k 个字符里可以任意选一个拿到末尾
• 操作自由度一下子大很多
• 最终你其实可以把字符串重新排列成任意顺序
• 那么字典序最小的结果当然就是：
  • 把所有字符排序后得到的字符串

所以这题的答案分成两类：

• 解法一：k = 1 时，枚举所有循环位移
• 解法二：k > 1 时，直接排序

虽然写起来像一个分类讨论，但这道题真正的难点恰恰就是：

要看出 k = 1 和 k > 1 的本质差异。

先理解：为什么 k = 1 只能得到循环位移？

假设：

s = "cba"
k = 1

因为前 1 个字符只有一个，也就是 'c'。

所以每次只能做：

"cba" -> "bac" -> "acb" -> "cba" -> ...

你会发现：

• 只能把最前面的字符挪到最后
• 本质上就是不断循环左移

所以最终所有可能结果，其实就是：

• cba
• bac
• acb

也就是字符串的所有循环位移。

因此：

• 只要把所有循环位移都枚举出来
• 找字典序最小的那个即可

再理解：为什么 k > 1 时可以直接排序？

这是这题最精华的地方。

当 k >= 2 时，你可以选择前两个字符中的任意一个移到末尾。

这意味着你不仅可以做普通的循环移动，还能“微调”字符相对顺序。

进一步可以证明：

• 当 k > 1 时
• 你可以通过一系列操作实现任意排列

既然最终可以排成任意顺序，那么为了让字典序最小：

• 直接把字符从小到大排序即可

你不一定要在考场上完整证明“任意排列都能实现”，但至少要记住这个经典结论：

• k = 1：只能轮转
• k > 1：可以排序

解法一：k = 1 时枚举所有循环位移

思路拆解

如果字符串长度是 n，那么它的循环位移一共只有 n 种：

• 从第 0 位开始
• 从第 1 位开始
• ...
• 从第 n - 1 位开始

第 i 种循环位移可以写成：

s.slice(i) + s.slice(0, i)

然后把这些候选字符串逐个比较，取最小值即可。

一步一步写出算法

第一步：先把答案初始化成原字符串

let answer = s

第二步：枚举每一个起点

for (let i = 1; i < s.length; i++) {
    const rotated = s.slice(i) + s.slice(0, i)
    if (rotated < answer) {
        answer = rotated
    }
}

这里从 1 开始枚举，是因为：

• i = 0 时就是原字符串本身
• 已经存在于 answer 里了

第三步：返回最优答案

return answer

代码实现（TypeScript）

function orderlyQueue(s: string, k: number): string {
    let answer = s

    for (let i = 1; i < s.length; i++) {
        const rotated = s.slice(i) + s.slice(0, i)
        if (rotated < answer) {
            answer = rotated
        }
    }

    return answer
}

复杂度分析

• 设字符串长度为 n
• 一共有 n 个循环位移
• 每次构造和比较字符串大约是 O(n)
• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

这一解法的优缺点

优点：

• 完全贴合 k = 1 的本质
• 很直观
• 很容易写对

缺点：

• 只适用于 k = 1
• 单独看不像完整解法，需要结合分类讨论

解法二：k > 1 时直接排序

思路拆解

当 k > 1 时，题目允许你在前 k 个字符中任选一个字符拿到末尾。

这使得操作空间足够大，最终可以实现任意排列。

所以字典序最小的字符串，就是：

• 把所有字符升序排序后拼接起来

例如：

s = "baaca"
k = 3

排序后得到：

"aaabc"

这就是最优答案。

一步一步写出算法

第一步：把字符串拆成字符数组

const chars = s.split('')

第二步：排序

chars.sort()

第三步：拼接回字符串

return chars.join('')

代码实现（TypeScript）

function orderlyQueue(s: string, k: number): string {
    return s.split('').sort().join('')
}

复杂度分析

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

这一解法的优缺点

优点：

• 代码极短
• 一旦看出结论，就非常好写

缺点：

• 难点不在实现，而在于证明 / 理解为什么 k > 1 可以排序

把两种情况合起来

完整做法其实就是：

• 如果 k === 1，枚举所有循环位移
• 否则，直接排序

完整代码实现（TypeScript）

function orderlyQueue(s: string, k: number): string {
    if (k === 1) {
        let answer = s

        for (let i = 1; i < s.length; i++) {
            const rotated = s.slice(i) + s.slice(0, i)
            if (rotated < answer) {
                answer = rotated
            }
        }

        return answer
    }

    return s.split('').sort().join('')
}

两种情况对比

这题不是“两个独立解法”，而是“一个完整解法里的两种分支情况”。

手动模拟一遍

示例 1：s = "cba", k = 1

因为 k = 1，只能做循环左移：

"cba"
"bac"
"acb"

按字典序比较：

"acb" < "bac" < "cba"

所以答案是：

"acb"

示例 2：s = "baaca", k = 3

因为 k > 1，最终可以实现任意排列。

所以直接把字符排序：

"baaca" -> "aaabc"

答案就是：

"aaabc"

面试时最容易错的点

1. 这题的真正难点是分类讨论

不是实现麻烦，而是要先看出：

• k = 1
• k > 1

是两类完全不同的问题。

2. k = 1 不是“随便重排”

很多人会误以为：

• 既然可以做很多次操作
• 那最后是不是总能排序？

不对。

当 k = 1 时，你每次只能拿最前面的字符到末尾，所以只能得到循环位移。

3. k > 1 时直接记住结论

考场上最重要的是记住：

• k > 1 时，答案就是排序后的字符串

如果你想更深入理解，可以把它和“相邻交换可以生成任意排列”这个思想联系起来。

4. 字典序比较是字符串直接比较

在 TypeScript / JavaScript 里：

if (a < b) {
    ...
}

对字符串就是按字典序比较。

一句话总结

这题的本质是：

k = 1 时只能轮转，k > 1 时可以排序。

所以：

• k = 1：枚举所有循环位移，取最小
• k > 1：直接把字符串排序

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个完整版本：

function orderlyQueue(s: string, k: number): string {
    if (k === 1) {
        let answer = s

        for (let i = 1; i < s.length; i++) {
            const rotated = s.slice(i) + s.slice(0, i)
            if (rotated < answer) {
                answer = rotated
            }
        }

        return answer
    }

    return s.split('').sort().join('')
}

因为这个版本：

• 把题目的本质分类写得很清楚
• 代码非常短
• 是这题公认的标准解法