读完本文，你能够去力扣拿下如下题目：
969.煎饼排序
-----------
烧饼排序是个很有意思的理论问题：假如盘子上有 n 块面积大小不一的烧饼，你如何用一把锅铲进行若干次翻转，让这些烧饼的大小有序（小的在上，大的在下）？
构想一下用锅铲翻转一堆烧饼的情景，其实是有一点限度的，咱们每次只能将最下面的若干块饼子翻转：
咱们的问题是，如何应用算法失去一个翻转序列，使得烧饼堆变得有序？
首先，须要把这个问题形象，用数组来示意烧饼堆：
如何解决这个问题呢？其实相似上篇文章 递归反转链表的一部分，这也是须要递归思维的。
一、思路剖析
为什么说这个问题有递归性质呢？比如说咱们须要实现这样一个函数：
// cakes 是一堆烧饼，函数会将前 n 个烧饼排序void sort(int[] cakes, int n);如果咱们找到了前 n 个烧饼中最大的那个，而后设法将这个饼子翻转到最底下：
那么，原问题的规模就能够减小，递归调用 pancakeSort(A, n-1) 即可：
接下来，对于下面的这 n - 1 块饼，如何排序呢？还是先从中找到最大的一块饼，而后把这块饼放到底下，再递归调用 pancakeSort(A, n-1-1)……
你看，这就是递归性质，总结一下思路就是：
1、找到 n 个饼中最大的那个。
2、把这个最大的饼移到最底下。
3、递归调用 pancakeSort(A, n - 1)。
base case：n == 1 时，排序 1 个饼时不须要翻转。
那么，最初剩下个问题，如何设法将某块烧饼翻到最初呢？
其实很简略，比方第 3 块饼是最大的，咱们想把它换到最初，也就是换到第 n 块。能够这样操作：
1、用锅铲将前 3 块饼翻转一下，这样最大的饼就翻到了最下面。
2、用锅铲将前 n 块饼全副翻转，这样最大的饼就翻到了第 n 块，也就是最初一块。
以上两个流程了解之后，根本就能够写出解法了，不过题目要求咱们写出具体的反转操作序列，这也很简略，只有在每次翻转烧饼时记录下来就行了。
二、代码实现
只有把上述的思路用代码实现即可，惟一须要留神的是，数组索引从 0 开始，而咱们要返回的后果是从 1 开始算的。
// 记录反转操作序列LinkedList<Integer> res = new LinkedList<>();List<Integer> pancakeSort(int[] cakes) { sort(cakes, cakes.length); return res;}void sort(int[] cakes, int n) { // base case 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--; }}通过方才的具体解释，这段代码应该是很清晰了。
算法的工夫复杂度很容易计算，因为递归调用的次数是 n，每次递归调用都须要一次 for 循环，工夫复杂度是 O(n)，所以总的复杂度是 O(n^2)。
最初，咱们能够思考一个问题：依照咱们这个思路，得出的操作序列长度应该为 2(n - 1)，因为每次递归都要进行 2 次翻转并记录操作，总共有 n 层递归，但因为 base case 间接返回后果，不进行翻转，所以最终的操作序列长度应该是固定的 2(n - 1)。
显然，这个后果不是最优的（最短的），比如说一堆煎饼 [3,2,4,1]，咱们的算法失去的翻转序列是 [3,4,2,3,1,2]，然而最快捷的翻转办法应该是 [2,3,4]：
初始状态 ：[3,2,4,1]
翻前 2 个：[2,3,4,1]
翻前 3 个：[4,3,2,1]
翻前 4 个：[1,2,3,4]
如果要求你的算法计算排序烧饼的最短操作序列，你该如何计算呢？或者说，解决这种求最优解法的问题，外围思路什么，肯定须要应用什么算法技巧呢？
无妨分享一下你的思考。