【递归】969. 煎饼排序

969. 煎饼排序

解题思路

• 寻找最大饼的索引： 遍历整个数组，找到当前未排序部分中最大的煎饼的索引。
• 第一次反转： 将最大的煎饼反转到最上面。
• 第二次反转： 将最大的煎饼反转到最下面。
• 递归调用： 对剩余的未排序煎饼进行递归排序，直到只剩一个煎饼

class Solution {
   
    List<Integer> res = new LinkedList<>();// 记录反转操作序列

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

    void sort(int[] cakes,int n){
   
        if(n == 1) return;

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

        for(int i= 0; i < n; i++){
   
            if(cakes[i] > maxCake){
   
                maxCakeIndex = i;
                maxCake = cakes[i];
            }
        }

        // 进行第一次反转 将最大的饼干反转到最上面
        reverse(cakes,0,maxCakeIndex);
        res.add(maxCakeIndex + 1);

        // 第二次反转 将最大的饼干  反转到最下面
        reverse(cakes,0,n - 1);
        res.add(n);

        // 递归调用
        sort(cakes,n - 1);
    }

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