31. 下一个排列

通过观察下一个排列数的规律，我们注意到要更改的那个数总是倒序第一个比右侧某个数小的第一个数，这样这个数才能变大，而且是尽可能小地变大。同时也因为这个定义，这个数右侧的数一定是从右往左看单调递增的，否则在右侧一定存在上述这样的数，这样就不符合定义了。这是一个关键的性质。又因为右侧是递增的，这个第一个数其实就是比它右侧相邻数大的那个数。

找到这个数后，我们需要用右侧比他大的最小的数和它交换。由于右侧的单调递增性质，这个数就是第一个比它大的数。

交换完之后，容易得证右侧的数还是符合从右向左看单调递增性质的，我们的目标是让右侧这个数整体最小，因此我们对右侧数列进行倒序操作即可。

注意到，如果找不到需要改变的数，证明当前数列已经是有序，下一个数就是最小的排列，我们也只需要进行倒叙操作即可。

class Solution {
    // 右侧单调递减性质
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int start = -1;
        for (int i = n - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                start = i - 1;
                break;
            }
        }
        if (start != -1) {
            for (int i = n - 1; i >= start; i--) {
                if (nums[i] > nums[start]) {
                    swap(nums, start, i);
                    break;
                }
            }
        }
        reverse(nums, start + 1, n - 1);
    }

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

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