31. 下一个排列（高频题）

31. 下一个排列

• 解题思路
• 代码

解题思路

数组问题嘛，双指针

我们会尽可能的将低位的数字变大，这样才符合「下一个排列」的定义。

为了更好理解，我们结合样例来分析，假设样例为 [1,3,5,4,1]：

1. 从后往前找，找到第一个下降的位置，记为 k。注意k 以后的位置是降序的。 在样例中就是找到 3

2. 找到大于当前元素的最后一个元素。 找到 4

3. 将两者交换。注意此时 k 以后的位置仍然是降序的。

4. 直接将 k 以后的部分翻转（变为升序）。

注意：如果在步骤 1 中找到头部还没找到，说明该序列已经是字典序最大的排列。按照题意，我们要将数组重新排列成最小的排列。

代码

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
//        从后往前找，找到第一个下降的位置
        while (k > 0 && nums[k - 1] >= nums[k]) {
            k--;
        }
        //注意：这里跳出来，k还要往前移动一位才是我们要的那个值，比如数组[1,3,5,4,1]，到这里k=5

//        没找到降序位置：说明该序列已经是字典序最大的排列
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
//            从 k 往后找，找到最小的比 k 要大的数
            //k - 1才是我们要的那个“[1,3,5,4,1]” k-1=3
            while (u < n - 1 && nums[u + 1] > nums[k - 1]) {
                u++;
            }
            //要交换的是k-1哦
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }

    /**
     * 反转 a到b的数组
     *
     * @param nums
     * @param a
     * @param b
     */
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

    /**
     * 原地交换俩元素
     *
     * @param nums
     * @param a
     * @param b
     */
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}