讀完本文概说，你可以去力扣拿下如下題目：
-----------
燒餅排序是個很有意思的實際問題：假設(shè)盤子上有 n 塊面積大小不一的燒餅剩胁，你如何用一把鍋鏟進行若干次翻轉(zhuǎn)声旺，讓這些燒餅的大小有序（小的在上斧拍，大的在下）己儒？
設(shè)想一下用鍋鏟翻轉(zhuǎn)一堆燒餅的情景记焊，其實是有一點限制的芳杏，我們每次只能將最上面的若干塊餅子翻轉(zhuǎn)：
我們的問題是，如何使用算法得到一個翻轉(zhuǎn)序列抡柿，使得燒餅堆變得有序舔琅？
首先，需要把這個問題抽象洲劣，用數(shù)組來表示燒餅堆：
如何解決這個問題呢备蚓？其實類似上篇文章 遞歸反轉(zhuǎn)鏈表的一部分，這也是需要遞歸思想的囱稽。
PS：我認真寫了 100 多篇原創(chuàng)郊尝，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄战惊，持續(xù)更新流昏。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了况凉。
一谚鄙、思路分析
為什么說這個問題有遞歸性質(zhì)呢？比如說我們需要實現(xiàn)這樣一個函數(shù)：
// cakes 是一堆燒餅刁绒，函數(shù)會將前 n 個燒餅排序
void sort(int[] cakes, int n);
如果我們找到了前 n 個燒餅中最大的那個襟锐，然后設(shè)法將這個餅子翻轉(zhuǎn)到最底下：
那么，原問題的規(guī)模就可以減小膛锭，遞歸調(diào)用 pancakeSort(A, n-1) 即可：
接下來，對于上面的這 n - 1 塊餅蚊荣，如何排序呢初狰？還是先從中找到最大的一塊餅，然后把這塊餅放到底下互例，再遞歸調(diào)用 pancakeSort(A, n-1-1)……
你看奢入，這就是遞歸性質(zhì)，總結(jié)一下思路就是：
1媳叨、找到 n 個餅中最大的那個腥光。
2、把這個最大的餅移到最底下糊秆。
3武福、遞歸調(diào)用 pancakeSort(A, n - 1)。
base case：n == 1 時痘番，排序 1 個餅時不需要翻轉(zhuǎn)捉片。
那么，最后剩下個問題汞舱，如何設(shè)法將某塊燒餅翻到最后呢伍纫？
其實很簡單，比如第 3 塊餅是最大的昂芜，我們想把它換到最后莹规，也就是換到第 n 塊∶谏瘢可以這樣操作：
1良漱、用鍋鏟將前 3 塊餅翻轉(zhuǎn)一下，這樣最大的餅就翻到了最上面腻扇。
2债热、用鍋鏟將前 n 塊餅全部翻轉(zhuǎn)，這樣最大的餅就翻到了第 n 塊幼苛，也就是最后一塊窒篱。
以上兩個流程理解之后，基本就可以寫出解法了，不過題目要求我們寫出具體的反轉(zhuǎn)操作序列墙杯，這也很簡單配并，只要在每次翻轉(zhuǎn)燒餅時記錄下來就行了。
二高镐、代碼實現(xiàn)
只要把上述的思路用代碼實現(xiàn)即可溉旋，唯一需要注意的是，數(shù)組索引從 0 開始嫉髓，而我們要返回的結(jié)果是從 1 開始算的观腊。
// 記錄反轉(zhuǎn)操作序列
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];
}
// 第一次翻轉(zhuǎn)，將最大餅翻到最上面
reverse(cakes, 0, maxCakeIndex);
res.add(maxCakeIndex + 1);
// 第二次翻轉(zhuǎn)算行，將最大餅翻到最下面
reverse(cakes, 0, n - 1);
res.add(n);
// 遞歸調(diào)用
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--;
}
}
通過剛才的詳細解釋梧油，這段代碼應(yīng)該是很清晰了。
算法的時間復雜度很容易計算州邢，因為遞歸調(diào)用的次數(shù)是 n儡陨，每次遞歸調(diào)用都需要一次 for 循環(huán)，時間復雜度是 O(n)量淌，所以總的復雜度是 O(n^2)骗村。
最后，我們可以思考一個問題?：按照我們這個思路呀枢，得出的操作序列長度應(yīng)該為? 2(n - 1)胚股，因為每次遞歸都要進行 2 次翻轉(zhuǎn)并記錄操作，總共有 n 層遞歸硫狞，但由于 base case 直接返回結(jié)果信轿，不進行翻轉(zhuǎn)，所以最終的操作序列長度應(yīng)該是固定的 2(n - 1)残吩。
顯然财忽，這個結(jié)果不是最優(yōu)的（最短的），比如說一堆煎餅 [3,2,4,1]泣侮，我們的算法得到的翻轉(zhuǎn)序列是 [3,4,2,3,1,2]即彪，但是最快捷的翻轉(zhuǎn)方法應(yīng)該是 [2,3,4]：
初始狀態(tài) ：[3,2,4,1]
翻前 2 個：[2,3,4,1]
翻前 3 個：[4,3,2,1]
翻前 4 個：[1,2,3,4]
如果要求你的算法計算排序燒餅的最短操作序列，你該如何計算呢活尊？或者說隶校，解決這種求最優(yōu)解法的問題，核心思路什么蛹锰，一定需要使用什么算法技巧呢深胳？
不妨分享一下你的思考。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章铜犬，手把手帶刷 200 道力扣題目舞终，建議收藏轻庆！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標星敛劝！
