煎饼排序

煎饼排序

969.煎饼排序

class Solution {
public:
    vector<int> res;
    vector<int> pancakeSort(vector<int>& arr) {
        int n=arr.size();
        cakeSort(arr, n);
        return res;
    }
    void cakeSort(vector<int>& arr, int n){
        //base case
        if(n==1) return;
        
        //寻找最大煎饼的索引
        int maxCake=0;
        int maxCakeIndex=0;
        for(int i=0;i<n;i++){
            if(arr[i]>maxCake){
                maxCakeIndex=i;
                maxCake=arr[i];
            }
        }
        //第一次翻转，将最大煎饼翻到最上面
        reverse(arr, 0, maxCakeIndex);
        //记录此次翻转
        res.push_back(maxCakeIndex+1);
        //第二次翻转，将最大煎饼翻到最下面
        reverse(arr, 0, n-1);
        //记录此次翻转
        res.push_back(n);

        //递归调用，翻转剩下的烧饼
        cakeSort(arr, n-1);
    }
    //翻转数组arr[i...j]的元素
    void reverse(vector<int>& arr, int i, int j){
        while(i<j){
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
};