LeetCode 969. 煎饼排序

2023-05-18 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 969. 煎饼排序

题意分析

给一个数组，唯一允许的操作是选一个 k，把前 k 个元素整体翻转（下标 0 到 k-1 首尾对调）。要求用一串这样的操作把数组变成升序，返回所选 k 的序列。

这个操作模型的特点是：只能从头部开始翻，翻转区间的左端永远是 0。所以无法直接把某个元素挪到任意位置，只能借助「翻到头部」这个中转。理解这一点，解法的两步结构就自然浮现了。

题目对操作次数有约束：不超过 10 * arr.length。这个上界很宽松——它是在告诉你不必追求最优解，只要能给出一个次数在 $10n$ 以内的合法方案即可。这条信息非常关键，它把一道看起来像「最少操作数」的难题降级成了构造题。事实上下面的贪心方案每个元素最多用两次翻转，总数不超过 $2n$，远在限制之内。

另一个重要约束是 arr 是 1 到 arr.length 的一个排列，所有元素互不相同。互异意味着「当前区间的最大值」唯一，不需要考虑相等元素的处理顺序。

边界要注意：数组长度为 1 时已经有序，返回空列表；某个元素恰好已经在正确位置时不该产生任何多余操作（虽然多翻也不算错，但会浪费次数且答案不够干净）；此外 k = 1 的翻转是恒等操作，不应出现在答案里。

解法：贪心翻转

核心思路

先想能不能直接构造：给定一个乱序数组，一次翻转能改变很多元素的位置，很难预测整体走向，从「怎么排最快」入手会陷入搜索。

换个角度，用归纳法的思路：如果能用有限次操作把最大的元素送到数组末尾，那么剩下的问题就是「对前 n-1 个元素做同样的事」，规模严格减一。而末尾的元素一旦就位，后续所有操作的 k 都小于它的下标，不会再动它——这是整个方案能成立的根本，也是必须向面试官讲清楚的正确性论证。

于是问题变成：怎么把当前区间 [0, size-1] 的最大值送到下标 size-1？ 由于翻转的左端固定为 0，只能分两步走。

第一步，设最大值在下标 maxIdx，执行 flip(maxIdx + 1)。翻转前 maxIdx + 1 个元素后，原本在 maxIdx 的最大值被送到下标 0。

第二步，执行 flip(size)。翻转前 size 个元素，位于下标 0 的最大值被送到下标 size - 1，正好是它该在的位置。

两步都以「翻到头部」为中转，这正是操作模型的限制所决定的唯一路径。

维持的循环不变量是：每轮开始时，下标区间 [size, n-1] 已经存放着最大的那几个数且已排好序，前 size 个元素是剩下的数（顺序任意）。初始时 size = n，右侧区间为空，成立；每轮把 [0, size-1] 的最大值送到 size-1，然后 size--，不变量得以维持。当 size 降到 1 时，前面只剩一个元素、它必然是最小的，整个数组有序。

还有两处剪枝值得单独说。若 maxIdx == size - 1，最大值本来就在目标位置，两次翻转都可以省掉，直接 continue。若 maxIdx == 0，最大值已经在头部，第一步可以省掉，只做第二步。这两个判断不是可有可无的优化——flip(1) 是恒等操作，把它写进答案属于无意义的操作。

解题步骤

外层循环用 size 从 arr.length 递减到 2：size 的语义是「尚未排好的前缀长度」，每轮把这个前缀里的最大值归位后减一。循环到 size == 1 时停止，因为单个元素的前缀天然有序，再做任何翻转都没有意义。

内层扫描 [0, size-1] 找最大值下标 maxIdx：只能在未排序前缀里找，绝不能扫到 size 之后——那部分已经归位，一旦被卷进来就会被后续翻转打乱。maxIdx 初始化为 0 并从 i = 1 开始比较，是标准的求最值下标写法。

若 maxIdx == size - 1 则 continue：最大值已在目标位置，两次翻转恰好会把它翻走再翻回来，属于纯粹的浪费。跳过它能让答案更短，在操作次数受限的题目里是应有的习惯。

若 maxIdx != 0，执行 reverse(arr, 0, maxIdx) 并记录 maxIdx + 1：把最大值送到头部。记录的是翻转长度而不是下标，两者相差 1，这是本题最高频的差一错误。若 maxIdx == 0 则跳过这一步，因为 flip(1) 什么也不改变。

执行 reverse(arr, 0, size - 1) 并记录 size：把头部的最大值送到 size - 1。这一步无条件执行——能走到这里说明 maxIdx != size - 1，最大值确实需要被搬到末尾。

reverse 用对撞双指针原地交换：left 从左端、right 从右端向中间靠拢，条件 left < right；写成 <= 会在两指针重合时做一次无害但多余的自我交换。

返回记录的翻转长度列表：题目只要操作序列，数组本身是否被修改并不影响判定，但保持数组同步更新是本算法能继续正确进行的前提。

以 arr = [3, 2, 4, 1] 走一遍。

第一轮，size = 4。扫描 [3,2,4,1] 找到最大值 4 在 maxIdx = 2。它不等于 size - 1 = 3，也不等于 0，所以先 reverse(0, 2)：前三个元素 [3,2,4] 翻成 [4,2,3]，数组变成 [4,2,3,1]，记录 maxIdx + 1 = 3。再 reverse(0, 3)：整个数组翻转成 [1,3,2,4]，记录 size = 4。此时 4 已在末尾就位。答案 [3, 4]。

第二轮，size = 3。只在前三个元素 [1,3,2] 里找最大值，得到 3 在 maxIdx = 1。它不等于 size - 1 = 2，也不等于 0，先 reverse(0, 1)：[1,3] 翻成 [3,1]，数组变成 [3,1,2,4]，记录 2。再 reverse(0, 2)：前三个 [3,1,2] 翻成 [2,1,3]，数组变成 [2,1,3,4]，记录 3。3 就位。答案 [3, 4, 2, 3]。

第三轮，size = 2。在 [2,1] 里找最大值，2 在 maxIdx = 0。它不等于 size - 1 = 1；由于 maxIdx == 0，跳过第一次翻转（省掉一次无意义的 flip(1)），直接 reverse(0, 1)：数组变成 [1,2,3,4]，记录 2。答案 [3, 4, 2, 3, 2]。

size 减到 1，循环结束。数组已是 [1,2,3,4]，返回的操作序列共 5 次，远小于上限 40。

注意第三轮如果没有 maxIdx != 0 的判断，会额外记录一个 1，虽然不改变数组也不会判错，但属于冗余操作。而第一轮如果把记录写成 maxIdx（即 2）而不是 maxIdx + 1（即 3），判题时按 flip(2) 执行会得到 [2,3,4,1]，与我们内部维护的数组不一致，后续所有操作全部失效。

代码实现

class Solution {
    // 先把最大值翻到数组头，再翻到目标位置。
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();

        for (int size = arr.length; size > 1; size--) {
            int maxIdx = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIdx]) {
                    maxIdx = i;
                }
            }

            if (maxIdx == size - 1) {
                continue;
            }

            if (maxIdx != 0) {
                reverse(arr, 0, maxIdx);
                res.add(maxIdx + 1);
            }

            reverse(arr, 0, size - 1);
            res.add(size);
        }

        return res;
    }

    private void reverse(int[] arr, int left, int right) {
        while (left < right) {
            int swapValue = arr[left];
            arr[left] = arr[right];
            arr[right] = swapValue;
            left++;
            right--;
        }
    }
}

func pancakeSort(arr []int) []int {
    // 先把最大值翻到数组头，再翻到目标位置。
    res := make([]int, 0)

    for size := len(arr); size > 1; size-- {
        maxIdx := 0
        for i := 1; i < size; i++ {
            if arr[i] > arr[maxIdx] {
                maxIdx = i
            }
        }

        if maxIdx == size-1 {
            continue
        }

        if maxIdx != 0 {
            reverse(arr, 0, maxIdx)
            res = append(res, maxIdx+1)
        }

        reverse(arr, 0, size-1)
        res = append(res, size)
    }

    return res
}

func reverse(arr []int, left int, right int) {
    for left < right {
        arr[left], arr[right] = arr[right], arr[left]
        left++
        right--
    }
}

复杂度分析

时间复杂度：$O(n^2)$，其中 $n$ 是数组长度。外层循环 $n-1$ 轮，每轮内部要扫描一次前缀找最大值（$O(size)$）并做至多两次翻转（同样是 $O(size)$），累加起来是 $1 + 2 + \cdots + n$ 量级。

空间复杂度：$O(1)$ 额外空间。翻转全部原地进行，只用了 size、maxIdx 和 reverse 里的两个指针；返回的操作序列长度不超过 $2n$，属于必要输出不计入。

关键点总结

先读操作次数上限再决定目标：本题给了 $10n$ 的宽松额度，说明要的是可行构造而非最优解。看到「不必最少」这类措辞就该放弃搜索、转向贪心构造，这个判断能省下大量时间。

「每次把最大的元素固定到末尾，问题规模减一」是选择排序的思想；换成受限操作模型后，归位后的后缀不再被触碰这一点必须显式论证，它是整个方案正确性的支柱。

当操作只能作用于固定端点时，把目标元素先送到那个端点当中转是通用套路，本题的「翻到头部再翻到尾部」两步法就是最典型的例子。

记录的是翻转长度而非下标，两者差 1；凡是「返回操作参数」的构造题，都要先确认参数的语义是长度、下标还是个数，面试时值得主动向面试官核对一句。

识别并跳过恒等操作（maxIdx == 0 时的 flip(1)、maxIdx == size-1 时的整对翻转），既让答案更短也体现了对操作语义的理解；在有操作次数硬上限的变体里，这类剪枝可能直接决定能否通过。

易错点总结

记录成 maxIdx 而不是 maxIdx + 1：[3,2,4,1] 第一轮的最大值在下标 2，正确应记 3；记成 2 时判题按 flip(2) 执行，得到 [2,3,4,1]，与内部数组不一致，后续操作全盘失效。

内层找最大值时扫到 arr.length 而不是 size：[1,2,3,4] 已排好的后缀会被重新选中并翻回前面，数组越翻越乱，永远无法收敛。

忘记 maxIdx == size - 1 的跳过：[1,2,3] 这类本已有序的输入会白白产生 4 次翻转，虽然结果仍正确，但在操作次数卡到 $2n$ 的变体里会直接超限。

忘记 maxIdx == 0 的跳过：会往答案里塞入 1，而 flip(1) 是恒等操作；[2,1] 会返回 [1,2] 而不是 [2]。

第二步写成 reverse(arr, 0, size)：右端越界一位，size == arr.length 时直接数组越界异常。

reverse 的循环条件写成 left <= right：奇数长度区间的中点会与自己交换一次，虽不改变结果但暴露了对对撞指针边界的理解模糊；若交换写成三行且中途用了同一个临时变量则完全无害，一旦改成异或交换 a ^= b ^= a ^= b 就会把中点清零。

外层循环条件写成 size > 0：size == 1 时会执行 reverse(0, 0) 并记录 1，多出一次恒等操作。

只记录操作而不真正修改数组：[3,2,4,1] 第二轮仍会在原始数组里找最大值，找到的是已经归位的 4，整个贪心的前提崩塌，返回的序列完全错误。

误以为要返回最少操作次数：本题只要求任意合法序列且次数不超过 $10n$，按最优化去搜索会指数级爆炸且完全没必要。

用 Arrays.sort 排好序再反推操作：排序本身不产生翻转序列，题目要的是操作过程而不是最终数组，这样交出去等于没解题。

每轮把最小值翻到前面而不是最大值翻到后面：思路本身可行，但翻转只能作用于前缀，最小值归位到下标 0 后，下一轮的翻转区间仍然包含它，会把已排好的元素重新打乱。

相似题目

题目	难度	考察点
344. 反转字符串	简单	只考对撞双指针原地翻转本身，是本题 `reverse` 辅助函数的裸考
541. 反转字符串 II	简单	按固定步长分段翻转，难点在末尾不足一段时的边界处理
189. 轮转数组	中等	三次整体翻转即可实现循环右移，展示翻转的组合威力
151. 反转字符串中的单词	中等	先整体翻转再逐个单词翻回，同样是「翻两次抵消」的思路
剑指 Offer 58 - I. 翻转单词顺序	简单	与 151 同题
48. 旋转图像	中等	转置加翻转两步完成原地旋转，同为「受限操作下的构造」
面试题 01.07. 旋转矩阵	中等	与 48 同题
75. 颜色分类	中等	值域只有三种时可一趟三指针原地排好，无需反复找最值
912. 排序数组	中等	无操作限制的通用排序，用快排或归并做到 $O(n \log n)$
977. 有序数组的平方	简单	利用原数组已有序的性质从两端向中间归并，不必真的排序