# 969.Pancake-Sorting

## 969. Pancake Sorting

## 题目地址

<https://leetcode.com/problems/pancake-sorting/>

## 题目描述

```
Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A.  We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A.  Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:
Input: [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: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. 

Example 2:
Input: [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.

Note:
1 <= A.length <= 100
A[i] is a permutation of [1, 2, ..., A.length]
```

## 代码

### Approach #1

**Explanation** Find the index `i` of the next maximum number `x`. Reverse `i + 1` numbers, so that the `x` will be at `A[0]` Reverse `x` numbers, so that `x` will be at `A[x - 1]`. Repeat this process `N` times.

**Update:** Actually, I didn't use the condition permutation of `[1,2,..., A.length]`. I searched in the descending order of `A`.

**Time Complexity**: O(N^2)

```java
class Solution {
  public List<Integer> pancakeSort(int[] A) {
    List<Integer> res = new ArrayList<>();
    for (int x = A.length, i; x > 0; --x) {
        for (i = 0; A[i] != x; ++i);
        reverse(A, i + 1); // 把最大的值移到A[0]
        res.add(i + 1);
        reverse(A, x);         // 把最大的移到A[end]
        res.add(x);
    }
    return res;
  }

  public void reverse(int[] A, int k) {
    for (int i = 0, j = k - 1; i < j; i++, j--) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
  }
}
```

### Approach #2 Sort Largest to Smallest

**Complexity Analysis**

* Time Complexity: O(N^2), where N*N* is the length of `A`.
* Space Complexity: O(N).

```java
class Solution {
  public List<Integer> pancakeSort(int[] A) {
        List<Integer> ans = new ArrayList();
    int N = A.length;

    Integer[] B = new Integer[N];
    for (int i = 0; i < N; i++) {
      B[i] = i + 1；
    }
    Arrays.sort(B, (i, j) -> A[j - 1] - A[i - 1]);

    for (int i: B) {
      for (int f: ans) {
        if (i <= f) {
          i = f + 1 - i;
        }
      }
      ans.add(i);
      ans.add(N--);
    }

    return ans;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/sort-algorithm/969.pancake-sorting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.