煎饼排序 图解题解

只能翻前 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 里。最大值若已在末位，整轮都该跳过，硬翻只会把排好的尾巴搅乱。它若已在顶，就得省掉第一翻，多翻那一张等于没翻，还会往答案塞个废数。碰上本就有序的数组，每轮都撞见「已在末位」，一次不翻、返回空串，就是题面第二个例子。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans;
        for (int i = n - 1; i > 0; --i) {
            int j = i;
            for (; j > 0 && arr[j] != i + 1; --j)
                ;
            if (j == i) continue;
            if (j > 0) {
                ans.push_back(j + 1);
                reverse(arr.begin(), arr.begin() + j + 1);
            }
            ans.push_back(i + 1);
            reverse(arr.begin(), arr.begin() + i + 1);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        List<Integer> ans = new ArrayList<>();
        for (int i = n - 1; i > 0; --i) {
            int j = i;
            for (; j > 0 && arr[j] != i + 1; --j)
                ;
            if (j < i) {
                if (j > 0) {
                    ans.add(j + 1);
                    reverse(arr, j);
                }
                ans.add(i + 1);
                reverse(arr, i);
            }
        }
        return ans;
    }

    private void reverse(int[] arr, int j) {
        for (int i = 0; i < j; ++i, --j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
}