969. 煎饼排序（算法思维系列）

969. 煎饼排序

• 题目
• 解题思路
• 代码

题目

给你一个整数数组 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 范围内的有效答案都将被判断为正确。

解题思路

第一次找到最大的煎饼，翻到最上面，然后再翻一次，把最大的煎饼翻到底部，重复上述过程。

代码

class Solution {
    List<Integer> res = new LinkedList<>();

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

    // 将前n块烧饼排序
    public void sort(int[] arr, int n) {
        if (n == 1) {
            return;
        }

        //寻找最大烧饼的索引
        int maxCake = 0;
        int maxCakeIndex = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] > maxCake) {
                maxCake = arr[i];
                maxCakeIndex = i;
            }
        }
        //把最大的烧饼反转到顶部
        reverse(arr, 0, maxCakeIndex);
        //记录下标。注意要比正常下标多1
        res.add(maxCakeIndex + 1);
        //再把最大烧饼反转到底部
        reverse(arr, 0, n - 1);
        res.add(n);

        //递归调用，翻转剩下的烧饼
        sort(arr, n - 1);


    }

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