网络异常，图片无法展示
|
给你一个整数数组 arr ，请使用 煎饼翻转 **完成对数组的排序。
一次煎饼翻转的执行过程如下：
- 选择一个整数
k，1 <= k <= arr.length - 反转子数组
arr[0...k-1]（下标从 0 开始）
例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
示例 1：
输入： [3,2,4,1] 输出： [4,2,4,3] 解释： 我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。 初始状态 arr = [3, 2, 4, 1] 第一次翻转后（k = 4）：arr = [1, 4, 2, 3] 第二次翻转后（k = 2）：arr = [4, 1, 2, 3] 第三次翻转后（k = 4）：arr = [3, 2, 1, 4] 第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。 复制代码
示例 2：
输入： [1,2,3] 输出： [] 解释： 输入已经排序，因此不需要翻转任何内容。 请注意，其他可能的答案，如 [3，3] ，也将被判断为正确。 复制代码
提示：
1 <= arr.length <= 1001 <= arr[i] <= arr.lengtharr中的所有整数互不相同（即，arr是从1到arr.length整数的一个排列）
因为每次翻转都是从下标 0 开始
想要完成排序，则需要每次将最大值放到未处理区间的末尾
而想要将最大值放到区间的末尾，则需要首先把该值翻转到下标 0 位置
然后再翻转 0 到目标位置区间
这样一遍操作，就完成了待处理区间最大值放到该区间末尾的操作
从数组末尾向前依次重复该过程，当处理完整个数组，则原数组有序
在处理过程中，记录每次翻转区间末尾下标位置+1，即为本次操作的 k 值
整个过程如下：
网络异常，图片无法展示
|
代码如下：
var pancakeSort = function(arr) { // 记录操作过程的结果数组 let res = [], // 当前处理位置下标 cur = arr.length-1; // 从后向前处理每一个位置 while(cur>0){ // 如果当前位置是待处理区间的最大值，则跳过 while(cur>0 && arr[cur] === Math.max(...arr.slice(0,cur+1))){ cur-- } if(cur===0) break; // 获取待处理区间的最大值 const maxInd = arr.indexOf(Math.max(...arr.slice(0,cur+1))); // 如果最大值不在下标 0 位置，则将其翻转到下标 0 位置 if(maxInd!==0){ arr = reverse(arr,0,maxInd); res.push(maxInd+1) } // 通过翻转下标 0 到目标下标，将当前区间最大值翻转到目标下标 arr = reverse(arr,0,cur); res.push(cur+1); cur--; } // 返回结果 return res; // 返回数组指定区间 function reverse(arr,left,right){ // 获取待翻转区间 const handleArr = arr.splice(left,right-left+1); // 进行翻转 handleArr.reverse(); // 将翻转后的区间插入原数组 arr.splice(left,0,...handleArr) return arr; } }; 复制代码
至此我们就完成了 leetcode-969-煎饼排序
如有任何问题或建议，欢迎留言讨论！
