969. 煎饼排序 - 力扣(LeetCode) (leetcode-cn.com)
从arr[]的末尾开始,逐个区间地去将对应区间的最大数字翻转到区间的末尾,reverse函数负责找出区间的最大数字,并通过两次翻转:
1、maxValue翻转到0,
2、maxValue从位置0翻转到区间末尾
注意返回的值是k,翻转的最大下标路径
public class Num969 { public static void main(String[] args) { int[] arr = {3,2,4,1}; List<Integer> ans = pancakeSort(arr); for(int number:ans){ System.out.print(number + " "); } } //这道题没有啥次数限制,就每次都把最大的那个数字找出来 public static List<Integer> pancakeSort(int[] arr) { List<Integer> ans = new ArrayList<>(); int len = arr.length; for(int i=len-1; i>=0; i--){ // 从区间上找,每次找当前区间的最大值,并将其反转到区间的最末尾 int rightIndex = i; reverse(arr, rightIndex, ans); } return ans; } public static void reverse(int[] arr, int rightIndex, List<Integer> ans){ // 最小的Index始终是0 int maxValue = arr[0]; int maxIndex = 0; for(int i=0; i<=rightIndex; i++){ // 找出[0, maxIndex]区间的最大值 if(arr[i] > maxValue){ maxValue = arr[i]; maxIndex = i; } } if(maxIndex == rightIndex){ //最大数已经在区间最右侧 return; } if(maxIndex!=0){ ans.add(maxIndex+1); } //反转子数组,两步: 1)先转到0 2)在转到rightIndex的位置 int left = 0; int right = maxIndex; while (left<right){ int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } ans.add(rightIndex+1); left = 0; right = rightIndex; while (left<right){ int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } } }