31. Next Permutation

class Solution {
    public void nextPermutation(int[] nums) {
        // [2, 9, 3, 1] -> [3, 1, 2, 9]

        int leftIndex = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) { // 出现了值更小的高位
                leftIndex = i; // 仅记录高位位置，不交换元素，因为 nums[i + 1] 不一定是右侧元素中稍微大于 nums[i] 的元素
                break;
            }
        }

        if (leftIndex != -1) {
            for (int i = nums.length - 1; i > leftIndex; i--) {
                if (nums[i] > nums[leftIndex]) {
                    swap(nums, i, leftIndex);
                    break;
                }
            }
        }

        // [3, 9, 2, 1]
        reverse(nums, leftIndex + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

由于题目要求需按照下一个更大的排列，那么容易想到通过交换数组中的元素实现，容易想到的是从右侧向左侧搜索，如果能把更低位的较大值与较高位的较小值交换，那么就能构成更大的序列，如数组：[4, 9, 5, 3]，容易想到的是将 4 与 9 交换得到：[9, 4, 5, 3]，但是通过观察原数组易知，交换至左侧元素的值应大于左侧元素且值应尽量接近左侧元素值，所以此时应该将 4 与 5 交换，以使得到的排列尽可能地接近原排列，交换后的数组为：[5, 9, 4, 3]，此时左侧元素值已经变大，那么此时还应该让剩下的元素组成的数值尽可能地小，此时只需将剩下的元素倒序即可（倒序前右侧元素非严格单调递减）。

References

31. Next Permutation