LeetCode 969. 煎饼排序

2023-05-18 HGNULB 约 5 分钟

文章信息 6 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 2-5 字节

题目描述

✅ 969. 煎饼排序

题意分析

数组是 1..n 的一个排列，允许的操作只有：选择长度 k，将前缀 arr[0..k-1] 整体反转。需要返回一串操作长度，使按顺序执行这些翻转后，数组变为升序。

题目接受不超过 10n 次翻转的任意合法方案，不要求操作最少。目标是构造一个操作数有上界、能够逐步固定正确位置的排序过程，不能只调用排序函数而不给出翻转方案。

解法：贪心翻转

核心思路

[!blue]

如果能够把当前未排序部分的最大值放到末尾，就能固定一个正确位置。限制是只能翻转前缀，不能任意交换两项；可以借助开头作为中转，先把最大值翻到下标 0，再把它翻到目标末尾。

用 size 表示当前未排序前缀的长度。找到其中最大值的位置 maxIdx 后，先翻转长度 maxIdx+1 的前缀，最大值就来到开头；再翻转长度 size 的前缀，它便来到下标 size-1。由于更大的元素已经固定在后缀，这正是它最终应该在的位置。

每轮开始时，后缀 arr[size..n-1] 已经有序且处在最终位置。两次翻转都不超过 size，不会碰到这个后缀；当前最大值就位后，后缀又向左扩展一项。将 size 减一继续，最终只剩一个元素，它自然也在正确位置。

若最大值已经在 size-1，本轮无需翻转；若它在开头，只需第二次翻转。总共至多处理 n-1 轮，每轮最多两次，操作数不超过 $2(n-1)$，满足题目的 10n 上限。

解题步骤

从 size = n 开始，逐轮缩小到 2，每轮扫描 [0,size) 找到最大值下标。

若最大值已经在当前末尾，直接进入下一轮。

若最大值不在开头，反转 [0,maxIdx]，并记录操作长度 maxIdx+1。

反转 [0,size-1]，记录操作长度 size，完成一个元素的归位。

每次记录操作时都要同步反转实际数组，后续寻找的是翻转后的最大值位置。已排序数组会逐轮跳过操作；单元素数组连外层循环也不执行，两者都可以返回空操作列表。

代码实现

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();

        for (int size = arr.length; size > 1; size--) {
            int maxIdx = 0;

            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIdx]) {
                    maxIdx = i;
                }
            }

            // 最大值已就位，直接缩短待排序前缀。
            if (maxIdx == size - 1) {
                continue;
            }

            if (maxIdx != 0) {
                reverse(arr, 0, maxIdx);
                res.add(maxIdx + 1);
            }

            // 将开头的最大值翻到末尾，之后不再动这个位置。
            reverse(arr, 0, size - 1);
            res.add(size);
        }

        return res;
    }

    private void reverse(int[] arr, int left, int right) {
        while (left < right) {
            int swapValue = arr[left];

            arr[left] = arr[right];
            arr[right] = swapValue;
            left++;
            right--;
        }
    }
}

func pancakeSort(arr []int) []int {
    res := make([]int, 0)

    for size := len(arr); size > 1; size-- {
        maxIdx := 0
        for i := 1; i < size; i++ {
            if arr[i] > arr[maxIdx] {
                maxIdx = i
            }
        }

        // 最大值已就位，直接缩短待排序前缀。
        if maxIdx == size-1 {
            continue
        }

        if maxIdx != 0 {
            reverse(arr, 0, maxIdx)
            res = append(res, maxIdx+1)
        }

        // 将开头的最大值翻到末尾，之后不再动这个位置。
        reverse(arr, 0, size-1)
        res = append(res, size)
    }

    return res
}

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

复杂度分析

时间复杂度：$O(n^2)$。长度为 size 的一轮，查找最大值和至多两次翻转均为 $O(size)$，累计为 $O(n+(n-1)+\cdots+2)$。

空间复杂度：除输出操作序列外为 $O(1)$，双指针翻转会原地修改数组。操作列表最多有 $2(n-1)$ 项，占 $O(n)$。

关键点总结

[!green]

开头是搬运最大值的中转位置，两次前缀翻转足以将它送到当前末尾。

正确性来自已排序后缀逐轮扩展，前缀中其他元素的临时顺序无需立即恢复。

答案记录前缀长度，而辅助函数接收左右下标，二者相差一位。

易错点总结

[!yellow]

记录了翻转但没有同步修改数组，会让后续最大值位置过期。

翻转超过当前未排序前缀，会破坏已经固定的位置。

把题目误当最少翻转次数，会增加不需要的搜索。

相似题目

题目	难度	关联与区别
344. 反转字符串	简单	前缀反转是唯一允许的基本操作，本题通过两次翻转把当前最大值送到末尾。
912. 排序数组	中等	本题不仅要得到有序数组，还需输出合法前缀翻转方案，不能直接调用普通排序代替。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/05273466

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！