烧饼排序算法

labuladong原创约 1226 字

本文讲解的例题

LeetCode	力扣	难度
969. Pancake Sorting	969. 煎饼排序	🟠

力扣第 969 题「煎饼排序」是个很有意思的实际问题：假设盘子上有 n 块面积大小不一的烧饼，你如何用一把锅铲进行若干次翻转，让这些烧饼的大小有序（小的在上，大的在下）？

设想一下用锅铲翻转一堆烧饼的情景，其实是有一点限制的，我们每次只能将最上面的若干块饼子翻转：

我们的问题是，如何使用算法得到一个翻转序列，使得烧饼堆变得有序？

首先，需要把这个问题抽象，用数组来表示烧饼堆：

969. 煎饼排序 | 力扣 | LeetCode |

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0...k-1]（下标从 0 开始）

例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。

提示：

1 <= arr.length <= 100
1 <= arr[i] <= arr.length
arr 中的所有整数互不相同（即，arr 是从 1 到 arr.length 整数的一个排列）

如何解决这个问题呢？其实类似上篇文章递归反转链表的一部分，这也是需要递归思想的。

一、思路分析

为什么说这个问题有递归性质呢？比如说我们需要实现这样一个函数：

java 🟢

// cakes 是一堆烧饼，函数会将前 n 个烧饼排序
void sort(int[] cakes, int n);

cpp 🤖

// cakes 是一堆烧饼，函数会将前 n 个烧饼排序
void sort(int cakes[], int n);

python 🤖

# cakes 是一堆烧饼，函数会将前 n 个烧饼排序
def sort(cakes: List[int], n: int):

go 🤖

// cakes 是一堆烧饼，函数会将前 n 个烧饼排序
func sort(cakes []int, n int) {}

javascript 🤖

// cakes 是一堆烧饼，函数会将前 n 个烧饼排序
var sort = function(cakes, n) {
};

如果我们找到了前 n 个烧饼中最大的那个，然后设法将这个饼子翻转到最底下：

那么，原问题的规模就可以减小，递归调用 pancakeSort(A, n-1) 即可：

接下来，对于上面的这 n - 1 块饼，如何排序呢？还是先从中找到最大的一块饼，然后把这块饼放到底下，再递归调用 pancakeSort(A, n-1-1)……

你看，这就是递归性质，总结一下思路就是：

1、找到 n 个饼中最大的那个。

2、把这个最大的饼移到最底下。

3、递归调用 pancakeSort(A, n - 1)。

base case：n == 1 时，排序 1 个饼时不需要翻转。

那么，最后剩下个问题，如何设法将某块烧饼翻到最后呢？

其实很简单，比如第 3 块饼是最大的，我们想把它换到最后，也就是换到第 n 块。可以这样操作：

1、用锅铲将前 3 块饼翻转一下，这样最大的饼就翻到了最上面。

2、用锅铲将前 n 块饼全部翻转，这样最大的饼就翻到了第 n 块，也就是最后一块。

以上两个流程理解之后，基本就可以写出解法了，不过题目要求我们写出具体的反转操作序列，这也很简单，只要在每次翻转烧饼时记录下来就行了。

二、代码实现

只要把上述的思路用代码实现即可，唯一需要注意的是，数组索引从 0 开始，而我们要返回的结果是从 1 开始算的。

java 🟢

class Solution {
    // 记录反转操作序列
    LinkedList<Integer> res = new LinkedList<>();

    public List<Integer> pancakeSort(int[] cakes) {
        sort(cakes, cakes.length);
        return res;
    }

    void sort(int[] cakes, int n) {
        // base case
        if (n == 1) return;
        
        // 寻找最大饼的索引
        int maxCake = 0;
        int maxCakeIndex = 0;
        for (int i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }
        
        // 第一次翻转，将最大饼翻到最上面
        reverse(cakes, 0, maxCakeIndex);
        res.add(maxCakeIndex + 1);
        // 第二次翻转，将最大饼翻到最下面
        reverse(cakes, 0, n - 1);
        res.add(n);

        // 递归调用
        sort(cakes, n - 1);
    }

    void reverse(int[] arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
}

cpp 🤖

class Solution {
public:
    // 记录反转操作序列
    vector<int> res;

    vector<int> pancakeSort(vector<int>& cakes) {
        sort(cakes, cakes.size());
        return res;
    }

    void sort(vector<int>& cakes, int n) {
        // base case
        if (n == 1) return;

        // 寻找最大饼的索引
        int maxCake = 0;
        int maxCakeIndex = 0;
        for (int i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }

        // 第一次翻转，将最大饼翻到最上面
        reverse(cakes, 0, maxCakeIndex);
        res.push_back(maxCakeIndex + 1);
        // 第二次翻转，将最大饼翻到最下面
        reverse(cakes, 0, n - 1);
        res.push_back(n);

        // 递归调用
        sort(cakes, n - 1);
    }

    void reverse(vector<int>& arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
};

python 🤖

from typing import List

class Solution:
    def pancakeSort(self, cakes: List[int]) -> List[int]:
        # 记录反转操作序列
        self.res = []
        self.sort(cakes, len(cakes))
        return self.res
    
    def sort(self, cakes: List[int], n: int) -> None:
        # base case
        if n == 1:
            return
        # 寻找最大饼的索引
        max_cake = 0
        max_cake_index = 0
        for i in range(n):
            if cakes[i] > max_cake:
                max_cake_index = i
                max_cake = cakes[i]
        # 第一次翻转，将最大饼翻到最上面
        self.reverse(cakes, 0, max_cake_index)
        self.res.append(max_cake_index + 1)
        # 第二次翻转，将最大饼翻到最下面
        self.reverse(cakes, 0, n - 1)
        self.res.append(n)

        # 递归调用
        self.sort(cakes, n - 1)
        
    def reverse(self, arr: List[int], i: int, j: int) -> None:
        while i < j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1

go 🤖

func pancakeSort(cakes []int) []int {
    res := []int{}
    sort(cakes, len(cakes), &res)
    return res
}

func sort(cakes []int, n int, res *[]int) {
    // base case
    if n == 1 {
        return
    }

    // 寻找最大饼的索引
    maxCake := 0
    maxCakeIndex := 0
    for i := 0; i < n; i++ {
        if cakes[i] > maxCake {
            maxCakeIndex = i
            maxCake = cakes[i]
        }
    }

    // 第一次翻转，将最大饼翻到最上面
    reverse(cakes, 0, maxCakeIndex)
    *res = append(*res, maxCakeIndex+1)
    
    // 第二次翻转，将最大饼翻到最下面
    reverse(cakes, 0, n-1)
    *res = append(*res, n)

    // 递归调用
    sort(cakes, n-1, res)
}

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

javascript 🤖

var pancakeSort = function(cakes) {
    // 记录反转操作序列
    const res = [];

    const sort = function(cakes, n) {
        // base case
        if (n == 1) return;
        
        // 寻找最大饼的索引
        let maxCake = 0;
        let maxCakeIndex = 0;
        for (let i = 0; i < n; i++)
            if (cakes[i] > maxCake) {
                maxCakeIndex = i;
                maxCake = cakes[i];
            }
        
        // 第一次翻转，将最大饼翻到最上面
        reverse(cakes, 0, maxCakeIndex);
        res.push(maxCakeIndex + 1);
        // 第二次翻转，将最大饼翻到最下面
        reverse(cakes, 0, n - 1);
        res.push(n);

        // 递归调用
        sort(cakes, n - 1);
    };

    const reverse = function(arr, i, j) {
        while (i < j) {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    };

    sort(cakes, cakes.length);
    return res;
};

通过刚才的详细解释，这段代码应该是很清晰了。

算法的时间复杂度很容易计算，因为递归调用的次数是 n，每次递归调用都需要一次 for 循环，时间复杂度是 O(n)，所以总的复杂度是 O(n^2)。

最后，我们可以思考一个问题：按照我们这个思路，得出的操作序列长度应该为 2(n - 1)，因为每次递归都要进行 2 次翻转并记录操作，总共有 n 层递归，但由于 base case 直接返回结果，不进行翻转，所以最终的操作序列长度应该是固定的 2(n - 1)。

显然，这个结果不是最优的（最短的），比如说一堆煎饼 [3,2,4,1]，我们的算法得到的翻转序列是 [3,4,2,3,1,2]，但是最快捷的翻转方法应该是 [2,3,4]：

初始状态 ：[3,2,4,1]
翻前 2 个：[2,3,4,1]
翻前 3 个：[4,3,2,1]
翻前 4 个：[1,2,3,4]

如果要求你的算法计算排序烧饼的最短操作序列，你该如何计算呢？或者说，解决这种求最优解法的问题，核心思路什么，一定需要使用什么算法技巧呢？

不妨分享一下你的思考。

烧饼排序算法

969. 煎饼排序 https://leetcode.cn/problems/pancake-sorting

969. Pancake Sorting https://leetcode.com/problems/pancake-sorting

一、思路分析

二、代码实现