执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。
如Example1， A = {3, 2, 4, 1}, output = {4, 2, 4, 3}， 也就是说先将A的前4个数翻转，再将新的A的前2个数翻转，然后前4个，最后是翻转前3个，最后使得A有序，也就是A = {1, 2, 3, 4}。
注意：结果不唯一，返回一个就可以。
思路：
1. 先处理最大值
(1) 先找到最大值所在的index1，然后0~index1的数翻转，使得最大值在首部；
(2) 结果集加入index1 + 1;
(3) 将0 ~ x - 1的数翻转，使得最大值在尾部；
(4) 结果集加入最大值。
2. 再处理次最大值
(1) 找到次大值所在的index2，然后0~index2的数翻转，使得次大值在首部；
(2) 结果集加入index2 + 1;
(3) 将0 ~ x - 1的数翻转，使得次大值在右起倒数第二个位置；
(4) 结果集加入次大值。
3. 再处理第3大的值、第4大的值...
稍微不同的是第3步，第几大值放在倒数第几位置。
时间复杂度：O(N²)，空间复杂度：O(N)。
1import java.util.ArrayList;
2import java.util.List;
3
4/**
5 * @author lxn
6 * @description 969. Pancake Sorting
7 * @create 2020-02-27 23:04
8 */
9public class Algorithm969 {
10 public static void main(String[] args) {
11 int[] A = {3, 2, 4, 1};
12 List<Integer> res = new Solution969().pancakeSort(A); // res = {3, 4, 2, 3, 1, 2, 1, 1}
13 }
14}
15
16class Solution969 {
17 public List<Integer> pancakeSort(int[] A) {
18 List<Integer> res = new ArrayList<>();
19
20 // Note说了A是由1, 2, ..., A.length组成，无序，所以A.length便是A中最大的值
21 for(int x = A.length; x >= 1; x--){
22 int i;
23 for(i = 0; A[i] != x; i++); // 先找到最大值的位置(本例中最大值是4，i = 2); 然后根据新的A找次大值3, i = 1; x = 2, i = 1; x = 1, i = 0;
24 reverse(A, i); // 将最大值4置换到数组首位置,A = {4, 2, 3, 1}; 次大值3置换到首部，A = {3, 1, 2, 4}; 2置换到首部, A = {2, 1, 3, 4}; x = 1, A ={1, 2, 3, 4};
25 res.add(i + 1); // 分别加入3，res = {3}; 加入2, res = {3, 4, 2}; 加入1, res = {3, 4, 2, 3, 1}; 加入1,res = {3, 4, 2, 3, 1, 2, 1}
26 reverse(A, x - 1);// 一开始x = 4, 置换所有的数, 这样最大值就能放到末尾, A = {1, 3, 2, 4}; x = 3,pos = 2,置换0~2的数，A = {2, 1, 3, 4}; x = 2,置换0~1的数，A = {1, 2, 3, 4}; x = 1, pos = 0,置换完还是一样, A = {1, 2, 3, 4};
27 res.add(x); // 分别加入4, res = {3, 4}; 加入3，res = {3, 4, 2, 3}; 加入2, res = {3, 4, 2, 3, 1, 2}; 加入1, res = {3, 4, 2, 3, 1, 2, 1, 1}
28 }
29 return res;
30 }
31
32 // index为0~pos的数, 以中间为轴，两头的翻转
33 private void reverse(int[] A, int pos){
34 for(int i = 0, j = pos; i < j; i++, j--){
35 int tmp = A[i];
36 A[i] = A[j];
37 A[j] = tmp;
38 }
39 }
40
41}
这里还有个疑问，就是：
Example 1：
Example 2 ：
我们的代码得到的结果似乎和Expected的不一样，但还是Accepted了，为什么呢？
答：其实题目说了：Any valid answer that sorts the array within 10 * A.length
flips will be judged as correct.
也就是结果不唯一。
而且Example 2里的解释也说了{3, 3}也是它的一个正确的解。
文章转载自程序媛的梦想，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
