题目

类型：贪心

解题思路

由于每次都对「某段前缀」进行整体翻转，并且规定了翻转次数在一定范围内的方案均为合法翻转方案，同时 arr 又是 1 到 n 的排列。可以很自然想到「冒泡排序」：每次确定未排序部分最右端的元素（最大值）。

假设下标 [k + 1, n - 1] 部分已有序，如果希望当前值 t 出现在某个位置 k 上，可以进行的操作为：

如果当前值 t 已在 k 上，无须进行操作；
如果当前值不在 k 上，根据当前值是否在数组头部（下标为 0）进行分情况讨论
- 当前值在数组头部（下标为 0），直接将 [0, k] 部分进行翻转（将 k + 1 加入答案中），即可将当前值 t 放到位置 k 上；
- 当前值不在数组头部（下标为 0），而是在 idx 位置上，需要先将 [0, idx] 部分进行翻转（将 idx + 1 加入答案中），这样使得当前值 t 出现数组头部（下标为 0），然后再将 [0, k] 部分进行翻转（将 k + 1 加入答案中），即可将当前值 t 放到位置 k 上。

翻转某个前缀的操作可使用「双指针」实现，复杂度为 O(n)。

代码

class Solution {
    // 煎饼排序
    // 这道题有这么一个提示：
    //      任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确
    // 提示你：用任何一种解法，只要能正确排序就行
    // 使用冒泡排序的思想，每一次把最大的扔在后面，排序剩下的子数组
    //      这道题是1 - n全排列 ，每次最大的就是 n - 1  -> 1
    // 举例： 3 2 4 1
    //       先找到 4 的位置，(翻转)将 4 放到 第一个位置 => 4 2 3 1
    //       (翻转) 0 - 4   =>1 3 2 4
    //       一次排序完成
    // 优化:比如 4 已经在它的位置上了，就不要再翻了
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new LinkedList<>();
        // 当前要排序的子数组下标为： 0 - max(不包括max)
        // 同时，由于全排列的原因：max 也是最大数字
        // 如果只剩 1 的话就不用排了
        for (int max = arr.length; max > 1; max--) {
            // 先找到当前要排序的数字=>最大数在哪
            int maxNumIndex;
            for (maxNumIndex = 0; arr[maxNumIndex] != max; maxNumIndex++) ;
            if (maxNumIndex == max - 1) {
                // 如果已经排好了，就不要排了
                continue;
            }
            // 如果当前要排序的数字，在 0 这个位置就省去了第一段排序
            // 否则就要换到 0 这个位置
            if (maxNumIndex != 0) {
                reverse(arr, 0, maxNumIndex);
                res.add(maxNumIndex + 1);
            }
            // 然后将 整个子数组反转
            reverse(arr, 0, max - 1);
            res.add(max);
        }
        return res;
    }
    private void reverse(int[] arr, int start, int end) {
        // 翻转 start 到 end 的数组
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}