/**
1. 字典序升序较小, 降序较大. 要找到下一个排列, 就要把一对升序调整为降序,并且恰好最小
2. 要恰好最小, 就要找最后一个升序的对(x , y), 并且保证他们的差最小
2.1 所以先找到 第一个 nums[x] < nums[x+1] 的点确定x , 此时可知 [x+1 ~ n] 是递减的
2.2 再找到 [x+1 ~ n] 中第一个比 nums[x]大的点 y
2.3 swap 他们,并刷新 [x+1 ~ n] 调整为升序

3. 如果x 不存在, 此时字典序最大, 将其整个翻转为最小

4. testcase:
null
1
123
321
231
312

*/

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int j = -1;
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]){
                j = i;
                break;
            }
        }

        if (j == -1) {
            reverse(nums, 0, n-1);
        } else {
            int p = -1;
            for (int i = n-1 ; i > j ; i --){
                if (nums[i] > nums[j]){
                    p = i;
                    break;
                }
            }
            swap(nums, j, p);
            reverse(nums, j+1, n-1);
        }
    }

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


    void reverse(int[] nums, int l, int r){
        while (l < r){
            int t = nums[l];
            nums[l++] = nums[r];
            nums[r--] = t;
        }
    }
}