翻煎饼

问题

https://leetcode-cn.com/problems/pancake-sorting

给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。

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

示例 1：

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

示例 2：

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

提示：
1 <= A.length <= 100
A[i] 是 [1, 2, …, A.length] 的排列

解法

递归

要把煎饼排列的有序，可以一次次地把最大的煎饼放到最下边，第一次把最大的煎饼放在最下边，第二次把最下边以上的煎饼按照刚才的套路把最大的煎饼放在最下边……，直到只剩一个煎饼就不用翻了，这时已经是有序的了。

上面有个基本的步骤，就是把一堆煎饼中的最大的弄到最下层。

可以分两步实现：

1. 找到最大的煎饼
2. 把最大的煎饼及以上的，翻转，这时最大的煎饼在最上方
3. 把整堆煎饼翻转，这时最大的煎饼在最下方

于是用递归实现如下：

result = []


def reverse(nums: list, start: int, end: int):
    nums[start:end] = nums[start:end][::-1]
    return nums


def turn_cakes(nums: list, layer: int):
    """
    翻转上 layer 层煎饼，将最大的煎饼翻到最下面
    :param nums: 列表，左侧的代表上面的煎饼，右侧的代表下面的煎饼
    :param layer: 从上往下layer层
    :return: 上layer层翻转过后全部的煎饼
    """
    if layer < 2:
        # 只有一层了，不翻了
        return nums

    # 找到最大的煎饼
    max_num = 0
    max_idx = 0
    for idx in range(layer):
        if nums[idx] > max_num:
            max_num = nums[idx]
            max_idx = idx
    # 最大的煎饼及以上，翻转，让最大的翻到最上面
    nums = reverse(nums, 0, max_idx + 1)
    result.append(max_idx + 1)

    # 对上面layer层翻转，让最大的煎饼翻到最下面
    nums = reverse(nums, 0, layer)
    result.append(layer)

    return turn_cakes(nums, layer - 1)


def handle(nums):
    turn_cakes(nums, len(nums))
    print(nums)
    return result


if __name__ == '__main__':
    cakes = [8, 3, 2, 5]
    print(handle(cakes))    # [1, 4, 1, 3, 1, 2]

递归时间复杂度 \(O(n)\)，查找最大值时间复杂度 \(O(n)\)，最终时间复杂度 \(O(n^2)\)。