969. 煎饼排序

通过递归思想解决问题（本题找到可行解即可，因此与示例的输出不一致，但仍能通过测试用例）

先把最大的烧饼放到最后面。怎么放呢？
- 找到最大烧饼对应的索引，翻转0到索引处的烧饼，先使最大烧饼放到最前面（并记录翻转处：1+索引值（因为结果从1开始计数））
- 然后翻转整个烧饼列，使得最前面的最大烧饼挪到最后面（并记录翻转处：最后面的n）
最大烧饼的位置不要动，翻转1到次大烧饼（因为是同样的问题，所以用递归）

class Solution {
private:
    vector<int> res{};
public:
    void sortN(vector<int> nums) {
//        递归结束的条件：只有一个烧饼了
        int n=nums.size();
        if (n == 1) return;

//        找到最大值对应的索引
        int maxIdx = max_element(nums.begin(), nums.end()) - nums.begin();
//        翻转开头到索引的烧饼
        reverse(nums.begin(), nums.begin() + maxIdx+1);
        res.push_back(1 + maxIdx); // 记录位置
        reverse(nums.begin(), nums.end()); // 翻转整个烧饼列
        res.push_back(n); // 记录位置

//        缩小烧饼列，翻转n-1个烧饼
        nums.assign(nums.begin(),nums.end()-1);
        sortN(nums);
    }

    vector<int> pancakeSort(vector<int> &arr) {
        sortN(arr);
        return res;
    }
};

class Solution(object):
    def pancakeSort(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        res=[]

        def dfs(arr):
            if len(arr)==1:
                return

            max_idx=arr.index(max(arr))
            arr=arr[:max_idx+1][::-1]+arr[max_idx+1:] # 翻转开头到最大索引的部分
            res.append(max_idx+1) # 记录位置
            arr=arr[::-1] # 翻转整个列表
            res.append(len(arr)) # 记录位置
            dfs(arr[:-1]) # 缩小规模，翻转n-1个烧饼
        dfs(arr)
        return res
# so=Solution()
# print(so.pancakeSort([3,2,4,1]))