题目描述
思路解析
一句话答案：LeetCode 969 煎饼排序：只能翻前 k 张，就每轮把没排好那段里的最大值先翻到顶、再翻到底沉入正确位置，记下每次的 k，n−1 轮排完，时间 O(n²)、空间 O(1)。
只能翻前 k 张，最后要我们交出什么
给一个 1 到 n 的排列（每个数恰好出现一次）arr。一次操作叫「煎饼翻转」：挑一个 k，把前 k 个元素整段反转。要返回一串 k 值，按顺序翻完让 arr 升序。题面 arr=[3,2,4,1]，一种答案 [3,4,2,3,2]，翻 5 次变 [1,2,3,4]；arr=[1,2,3] 本就有序，返回空串。答案不唯一，翻转次数不超 10n 都算对。
为什么不能像普通排序那样随手换两个数
普通排序想换哪两个位置就换，这题的手被绑住——唯一动作是反转前缀，想挪中间某个数，得连它前面一整串一起翻。穷举所有翻转组合去凑有序，序列可以很长、可能性指数级膨胀，根本试不完。得找一套照着走就一定排好的翻法，让每个数固定几步落位。
怎么用两次翻转，把一张饼精准送到底
前缀翻转藏着一根杠杆：你没法直接把某张饼放到末位，却能借下标 0 中转。想让最大的饼落到最末位，先翻一个前缀把它带到最顶（下标 0），再翻一个更长的前缀把它一路带到末位，两翻就位。
于是整体走贪心加模拟：每一轮只挑当下最该做的一件事做、照规则一轮轮往下推，盯住还没排好那段前缀里的最大值，沉到这段末尾，排好的尾巴长一节、前缀缩一格，n−1 轮后全部归位。只管最大值：它沉到底后不再挪动，剩下的短前缀又是同一问题的缩小版。
一轮里的两次翻转，k 该记成几
具体到一轮，设未排前缀是下标 0 到 i。从右往左找到这轮最大值所在下标 j，分三种情形：已在末位（j 等于 i）什么都不做；在中间（j 落在 0 和 i 之间），先翻前 j+1 张送到顶、再翻前 i+1 张送到底；已在顶（j 等于 0）省掉第一翻，直接翻前 i+1 张送到底。记进答案的是「张数」j+1、区间 [0, j]，写成 j 就翻错一段。
[3,2,4,1] 五次翻转，k 序列一步步长出来
第 1 轮前缀是下标 0 到 3，最大值 4 在下标 2、不在末位：先翻前 3 张（记 3），[3,2,4,1] 变 [4,2,3,1]，4 到顶；再翻前 4 张（记 4）变 [1,3,2,4]，4 落到下标 3 归位，答案 [3,4]。第 2 轮前缀缩到下标 0 到 2，最大值 3 在下标 1：先翻前 2 张（记 2）、再翻前 3 张（记 3）得 [2,1,3,4]，3 归位到下标 2，答案 [3,4,2,3]。
第 3 轮前缀只剩下标 0 到 1，2 在下标 0——已在顶，省掉第一翻，直接翻前 2 张（记 2）变 [1,2,3,4]，2 落到下标 1、1 顺势回下标 0，整摞升序。把记下的张数连起来就是 [3,4,2,3,2]，共 5 次翻转，对上题面。
n−1 轮各扫一遍，边界上别多翻那一下
一共 n−1 轮，每轮扫一遍前缀找最大再翻，各 O(n)，合起来时间 O(n²)；翻转原地进行、空间 O(1)。每轮最多翻两次，总次数不超过 2(n−1)，落在 10n 里。最大值若已在末位，整轮都该跳过，硬翻只会把排好的尾巴搅乱。它若已在顶，就得省掉第一翻，多翻那一张等于没翻，还会往答案塞个废数。碰上本就有序的数组，每轮都撞见「已在末位」，一次不翻、返回空串，就是题面第二个例子。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套「找最大，翻到顶，再翻到底」，下面每一轮都在套它。
这就是要排的一摞煎饼，数组 [3,2,4,1]。我们一轮一轮地把当前最大的那张归位，紫色框出的就是还没排好的前缀。
第 1 轮，未排前缀是 [下标 0 到 3]。先看下标 0 的 3，暂时当作最大。
看下标 1 的 2，比 3 小，最大还是 3。
看下标 2 的 4，比刚才的 3 大，最大刷新成 4。
看下标 3 的 1，比 4 小，最大还是 4。
这轮最大的饼是 4，它最终该躺在下标 3（前缀的最末位）。分两步翻过去。
第一翻：翻最上面 3 张（k=3），把 4 先翻到最顶。高亮的就是要翻的区间。
翻完前 3 张，4 现在到了最顶（下标 0）。
第二翻：翻最上面 4 张（k=4），把顶上的 4 一路翻到下标 3。
翻完前 4 张，4 归位在下标 3（蓝色），已排好的尾巴又长了一节。
第 2 轮，未排前缀是 [下标 0 到 2]。先看下标 0 的 1，暂时当作最大。
看下标 1 的 3，比刚才的 1 大，最大刷新成 3。
看下标 2 的 2，比 3 小，最大还是 3。
这轮最大的饼是 3，它最终该躺在下标 2（前缀的最末位）。分两步翻过去。
第一翻：翻最上面 2 张（k=2），把 3 先翻到最顶。高亮的就是要翻的区间。
翻完前 2 张，3 现在到了最顶（下标 0）。
第二翻：翻最上面 3 张（k=3），把顶上的 3 一路翻到下标 2。
翻完前 3 张，3 归位在下标 2（蓝色），已排好的尾巴又长了一节。
第 3 轮，未排前缀是 [下标 0 到 1]。先看下标 0 的 2，暂时当作最大。
看下标 1 的 1，比 2 小，最大还是 2。
这轮最大是 2，而且它已经在最顶（下标 0）了，第一次翻转可以省掉，直接做第二翻。
第二翻：翻最上面 2 张（k=2），把顶上的 2 一路翻到下标 1。
翻完前 2 张，2 归位在下标 1。最小的 1 也顺势落到下标 0，整摞全好了。
全部升序排好！[1,2,3,4]。一路记录的翻转张数连起来就是答案：k 序列 3,4,2,3,2，一共 5 次翻转。
有序、两元素、单元素三种边界先想清，省得现场翻车。
两个高频追问：次数上界稳在限制内，但「最少次数」是另一个难题。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def pancakeSort(self, arr: List[int]) -> List[int]: def reverse(arr, j): i = 0 while i < j: arr[i], arr[j] = arr[j], arr[i] i, j = i + 1, j - 1 n = len(arr) ans = [] for i in range(n - 1, 0, -1): j = i while j > 0 and arr[j] != i + 1: j -= 1 if j < i: if j > 0: ans.append(j + 1) reverse(arr, j) ans.append(i + 1) reverse(arr, i) return ans复杂度
- 时间：O(n²)，共 n-1 轮，每轮扫一遍前缀找最大并翻转，都是 O(n)
- 空间：O(1)，原地翻转，只用几个下标变量；答案数组不计入额外空间
- 翻转次数：≤ 2(n-1)，每轮最多两翻，远在 10n 的限制内
易错点
面试追问把动画讲成自己的话
追问这套贪心的翻转次数上界是多少？会超题目限制吗？
追问能不能找到「最少翻转次数」的解？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
子串能表示从 1 到 N 数字的二进制串
LeetCode 1016 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题