LeetCode - 969. Pancake Sorting

原题：https://leetcode-cn.com/problems/pancake-sorting/
难度：medium

解题思路：题目并不要求找到最优解，任意解即可。这里想到的是类似于冒泡的思路，每次翻转都先把最大的数字翻转到第一位，然后在翻转一次将最大的置于最后，达到冒泡的效果。以给定的测试用例可以进行以下翻转：

1. k=3，将4置于第一位：4 2 3 1
2. k=4，此时4置于正确的位置：1 3 2 4
3. 接下来只需考虑前3个数即可，此时3为前3个数中的最大值，k=2： 3 1 2 4
4. k=3: 2 1 3 4
5. k=2: 1 2 3 4，结束

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> result = new ArrayList<>();
        for(int i = arr.length; i > 1; i --) {
            int idx = findMax(arr, i);
            if(idx == i - 1) {
                continue;
            }
            if(idx != 0) {
                swap(arr, idx + 1);
                result.add(idx + 1);
            }
            result.add(i);
            swap(arr, i);
        }
        return result;
    }

    private int findMax(int[]a, int last) {
        int max = -1;
        int idx = 0;
        for(int i = 0; i < last; i ++) {
            if(a[i] > max) {
                max = a[i];
                idx = i;
            }
        }
        return idx;
    }

    private void swap(int[]a, int last) {
        for(int i = 0; i < last / 2; i ++) {
            int temp = a[i];
            a[i] = a[last - 1 - i];
            a[last - 1 - i] = temp;
        }
    }
}

执行用时： 2 ms , 在所有 Java 提交中击败了 68.67% 的用户
内存消耗： 38.6 MB , 在所有 Java 提交中击败了 68.42% 的用户