# 烧饼排序算法

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

969. Pancake Sorting | 🟠 |

LeetCode problem 969, "Pancake Sorting," is an interesting practical problem: Suppose you have `n`

pancakes of **different sizes** on a plate. How can you use a spatula to flip them several times to arrange the pancakes in order (smaller ones on top, larger ones at the bottom)?

Imagine flipping a stack of pancakes with a spatula. There's a limitation: you can only flip the top several pancakes at a time:

Our question is, **how can we use an algorithm to get a sequence of flips that will sort the stack of pancakes**?

First, we need to abstract this problem and represent the stack of pancakes using an array:

**969. Pancake Sorting** | 力扣 | LeetCode |

Given an array of integers `arr`

, sort the array by performing a series of **pancake flips**.

In one pancake flip we do the following steps:

- Choose an integer
`k`

where`1 <= k <= arr.length`

. - Reverse the sub-array
`arr[0...k-1]`

(**0-indexed**).

For example, if `arr = [3,2,1,4]`

and we performed a pancake flip choosing `k = 3`

, we reverse the sub-array `[3,2,1]`

, so `arr = [`

after the pancake flip at __1__,__2__,__3__,4]`k = 3`

.

Return *an array of the *`k`

*-values corresponding to a sequence of pancake flips that sort *`arr`

. Any valid answer that sorts the array within `10 * arr.length`

flips will be judged as correct.

**Example 1:**

Input:arr = [3,2,4,1]Output:[4,2,4,3]Explanation:We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: arr = [3, 2, 4, 1] After 1st flip (k = 4): arr = [1,4,2,3] After 2nd flip (k = 2): arr = [4,1, 2, 3] After 3rd flip (k = 4): arr = [3,2,1,4] After 4th flip (k = 3): arr = [1,2,3, 4], which is sorted.

**Example 2:**

Input:arr = [1,2,3]Output:[]Explanation:The input is already sorted, so there is no need to flip anything. Note that other answers, such as [3, 3], would also be accepted.

**Constraints:**

`1 <= arr.length <= 100`

`1 <= arr[i] <= arr.length`

- All integers in
`arr`

are unique (i.e.`arr`

is a permutation of the integers from`1`

to`arr.length`

).

How do we solve this problem? Similar to the previous article Recursive Reversal of a Linked List Segment, this also requires **recursive thinking**.

### I. Thought Analysis

Why is this problem recursive in nature? For example, suppose we need to implement a function like this:

```
// cakes is a pile of pancakes, the function will sort the first n pancakes
void sort(int[] cakes, int n);
```

```
// cakes is a pile of pancakes, the function will sort the first n pancakes
void sort(int cakes[], int n);
```

```
# cakes is a pile of pancakes, the function will sort the first n pancakes
def sort(cakes: List[int], n: int):
```

```
// cakes is a pile of pancakes, the function will sort the first n pancakes
func sort(cakes []int, n int) {}
```

```
// cakes is a pile of pancakes, the function will sort the first n pancakes
var sort = function(cakes, n) {
};
```

If we find the largest pancake among the first `n`

pancakes and then flip it to the bottom:

The size of the original problem can be reduced, and we can recursively call `pancakeSort(A, n-1)`

:

Next, how do we sort the remaining `n - 1`

pancakes? We still find the largest pancake among them, move it to the bottom, and then recursively call `pancakeSort(A, n-1-1)`

...

You see, this is the nature of recursion. To summarize the approach:

- Find the largest pancake among the
`n`

pancakes. - Move this largest pancake to the bottom.
- Recursively call
`pancakeSort(A, n - 1)`

.

Base case: When `n == 1`

, sorting one pancake requires no flipping.

So, the last question remains: **How do we move a specific pancake to the end**?

It's quite simple. For example, if the 3rd pancake is the largest and we want to move it to the end (i.e., the `n`

th position), we can do the following:

- Flip the first 3 pancakes with a spatula, so the largest pancake moves to the top.
- Flip all the first
`n`

pancakes, so the largest pancake moves to the`n`

th position, which is the last one.

Once you understand these two steps, you can basically write the solution. However, the problem requires us to write out the specific sequence of flip operations, which is also simple. Just record each flip operation.

### II. Code Implementation

You just need to implement the above approach in code. The only thing to note is that array indices start from 0, but the results we return should be counted from 1.

```
class Solution {
// record the sequence of flip operations
LinkedList<Integer> res = new LinkedList<>();
public List<Integer> pancakeSort(int[] cakes) {
sort(cakes, cakes.length);
return res;
}
void sort(int[] cakes, int n) {
// base case
if (n == 1) return;
// find the index of the largest cake
int maxCake = 0;
int maxCakeIndex = 0;
for (int i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// first flip, flip the largest cake to the top
reverse(cakes, 0, maxCakeIndex);
res.add(maxCakeIndex + 1);
// second flip, flip the largest cake to the bottom
reverse(cakes, 0, n - 1);
res.add(n);
// recursive call
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--;
}
}
}
```

```
class Solution {
public:
// record the sequence of reversal operations
vector<int> res;
vector<int> pancakeSort(vector<int>& cakes) {
sort(cakes, cakes.size());
return res;
}
void sort(vector<int>& cakes, int n) {
// base case
if (n == 1) return;
// find the index of the largest cake
int maxCake = 0;
int maxCakeIndex = 0;
for (int i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// first reversal, flip the largest cake to the top
reverse(cakes, 0, maxCakeIndex);
res.push_back(maxCakeIndex + 1);
// second reversal, flip the largest cake to the bottom
reverse(cakes, 0, n - 1);
res.push_back(n);
// recursive call
sort(cakes, n - 1);
}
void reverse(vector<int>& arr, int i, int j) {
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
};
```

```
from typing import List
class Solution:
def pancakeSort(self, cakes: List[int]) -> List[int]:
# record the sequence of reversal operations
self.res = []
self.sort(cakes, len(cakes))
return self.res
def sort(self, cakes: List[int], n: int) -> None:
# base case
if n == 1:
return
# find the index of the largest cake
max_cake = 0
max_cake_index = 0
for i in range(n):
if cakes[i] > max_cake:
max_cake_index = i
max_cake = cakes[i]
# first reversal, flip the largest cake to the top
self.reverse(cakes, 0, max_cake_index)
self.res.append(max_cake_index + 1)
# second reversal, flip the largest cake to the bottom
self.reverse(cakes, 0, n - 1)
self.res.append(n)
# recursive call
self.sort(cakes, n - 1)
def reverse(self, arr: List[int], i: int, j: int) -> None:
while i < j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
```

```
func pancakeSort(cakes []int) []int {
res := []int{}
sort(cakes, len(cakes), &res)
return res
}
func sort(cakes []int, n int, res *[]int) {
// base case
if n == 1 {
return
}
// find the index of the largest cake
maxCake := 0
maxCakeIndex := 0
for i := 0; i < n; i++ {
if cakes[i] > maxCake {
maxCakeIndex = i
maxCake = cakes[i]
}
}
// first flip, flip the largest cake to the top
reverse(cakes, 0, maxCakeIndex)
*res = append(*res, maxCakeIndex+1)
// second flip, flip the largest cake to the bottom
reverse(cakes, 0, n-1)
*res = append(*res, n)
// recursive call
sort(cakes, n-1, res)
}
func reverse(arr []int, i int, j int) {
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
```

```
var pancakeSort = function(cakes) {
// record the sequence of flip operations
const res = [];
const sort = function(cakes, n) {
// base case
if (n == 1) return;
// find the index of the largest pancake
let maxCake = 0;
let maxCakeIndex = 0;
for (let i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// first flip, flip the largest pancake to the top
reverse(cakes, 0, maxCakeIndex);
res.push(maxCakeIndex + 1);
// second flip, flip the largest pancake to the bottom
reverse(cakes, 0, n - 1);
res.push(n);
// recursive call
sort(cakes, n - 1);
};
const reverse = function(arr, i, j) {
while (i < j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
};
sort(cakes, cakes.length);
return res;
};
```

With the detailed explanation above, this code should be quite clear now.

The time complexity of the algorithm is easy to calculate. Since the number of recursive calls is `n`

and each recursive call involves a for loop, the time complexity is O(n). Therefore, the overall complexity is O(n^2).

**Finally, let's ponder a question**: Following our approach, the length of the operation sequence should be `2(n - 1)`

. This is because each recursive call performs 2 flips and records the operations, and there are `n`

levels of recursion. However, due to the base case returning the result directly without flipping, the final operation sequence length should be a fixed `2(n - 1)`

.

Clearly, this result is not optimal (the shortest). For example, with a stack of pancakes `[3,2,4,1]`

, our algorithm yields the flip sequence `[3,4,2,3,1,2]`

, but the quickest flip method should be `[2,3,4]`

:

```
Initial state: [3,2,4,1]
Flip first 2: [2,3,4,1]
Flip first 3: [4,3,2,1]
Flip first 4: [1,2,3,4]
```

If you were asked to design an algorithm to compute the **shortest** operation sequence for sorting pancakes, how would you approach it? Or, more generally, what is the core idea for solving such optimization problems, and what algorithmic techniques might be essential?

Feel free to share your thoughts.