煎饼排序 图解题解

这道题到底在问什么

输入

arr=[3,2,4,1]

输出

[3,4,2,3,2]　（5 次翻转后变成 [1,2,3,4]）

输入

arr=[1,2,3]

输出

[]　（本来就有序，不用翻）

最优解：一步一步想明白

1. 3记牢这套「找最大，翻到顶，再翻到底」，下面每一轮都在套它。
2. 4这就是要排的一摞煎饼，数组 [3,2,4,1]。我们一轮一轮地把当前最大的那张归位，紫色框出的就是还没排好的前缀。
3. 5第 1 轮，未排前缀是 [下标 0 到 3]。先看下标 0 的 3，暂时当作最大。
4. 6看下标 1 的 2，比 3 小，最大还是 3。
5. 7看下标 2 的 4，比刚才的 3 大，最大刷新成 4。
6. 8看下标 3 的 1，比 4 小，最大还是 4。
7. 9这轮最大的饼是 4，它最终该躺在下标 3（前缀的最末位）。分两步翻过去。
8. 10第一翻：翻最上面 3 张（k=3），把 4 先翻到最顶。高亮的就是要翻的区间。
9. 11翻完前 3 张，4 现在到了最顶（下标 0）。
10. 12第二翻：翻最上面 4 张（k=4），把顶上的 4 一路翻到下标 3。
11. 13翻完前 4 张，4 归位在下标 3（蓝色），已排好的尾巴又长了一节。
12. 14第 2 轮，未排前缀是 [下标 0 到 2]。先看下标 0 的 1，暂时当作最大。
13. 15看下标 1 的 3，比刚才的 1 大，最大刷新成 3。
14. 16看下标 2 的 2，比 3 小，最大还是 3。
15. 17这轮最大的饼是 3，它最终该躺在下标 2（前缀的最末位）。分两步翻过去。
16. 18第一翻：翻最上面 2 张（k=2），把 3 先翻到最顶。高亮的就是要翻的区间。
17. 19翻完前 2 张，3 现在到了最顶（下标 0）。
18. 20第二翻：翻最上面 3 张（k=3），把顶上的 3 一路翻到下标 2。
19. 21翻完前 3 张，3 归位在下标 2（蓝色），已排好的尾巴又长了一节。
20. 22第 3 轮，未排前缀是 [下标 0 到 1]。先看下标 0 的 2，暂时当作最大。
21. 23看下标 1 的 1，比 2 小，最大还是 2。
22. 24这轮最大是 2，而且它已经在最顶（下标 0）了，第一次翻转可以省掉，直接做第二翻。
23. 25第二翻：翻最上面 2 张（k=2），把顶上的 2 一路翻到下标 1。
24. 26翻完前 2 张，2 归位在下标 1。最小的 1 也顺势落到下标 0，整摞全好了。
25. 27全部升序排好！[1,2,3,4]。一路记录的翻转张数连起来就是答案：k 序列 3,4,2,3,2，一共 5 次翻转。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
        }
    }
}

复杂度

面试官可能追问