---

0969. 煎饼排序

• 标签：贪心、数组、双指针、排序
• 难度：中等

题目链接

• 0969. 煎饼排序 - 力扣

题目大意

描述：

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

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

• 选择一个整数 $k$，$1 \le k \le arr$.length$。
• 反转子数组 $arr[...k-1]$（下标从 0 开始）。

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

要求：

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

说明：

• $1 \le arr.length \le 10^{3}$。
• $1 \le arr[i] \le arr.length$。
• $arr$ 中的所有整数互不相同（即，$arr$ 是从 $1$ 到 $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：贪心

煎饼排序的核心思想是：每次找到未排序部分的最大值，将其翻转到最前面，再翻转到正确的位置。

1. 从后向前排序：从数组末尾开始，每次将最大的未排序元素放到正确位置。
2. 两次翻转：
   • 第一次翻转：将最大元素翻转到数组开头（翻转 $[0, maxIndex]$）
   • 第二次翻转：将最大元素翻转到目标位置（翻转 $[0, i]$）
3. 重复过程：对剩余未排序部分重复上述过程。

优化：如果当前最大元素已经在正确位置，则跳过。

思路 1：代码

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        result = []
        n = len(arr)
        
        # 从后向前排序
        for target in range(n, 0, -1):
            # 找到目标值的位置
            max_index = arr.index(target)
            
            # 如果已经在正确位置，跳过
            if max_index == target - 1:
                continue
            
            # 如果不在开头，先翻转到开头
            if max_index != 0:
                result.append(max_index + 1)
                arr[:max_index + 1] = arr[:max_index + 1][::-1]
            
            # 翻转到目标位置
            result.append(target)
            arr[:target] = arr[:target][::-1]
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组长度。外层循环 $O(n)$ 次，每次查找和翻转需要 $O(n)$ 时间。
• 空间复杂度：$O(1)$，不考虑返回结果的空间。