两次遍历

• 这道题的目的就是要让变化的幅度尽可能小，所以应该从个位向十位百位这样的顺序遍历

• 从后往前遍历， 找到第一个递减的点 i （如果找不到，说明整个数组从前往后是一直降序的，直接整体反转）

  

• 再从后往前遍历， 找到第一个大于i的点 j

• 交换 i 和 j ， 可以证明此时 (i + 1, n) 还是 降序的， 可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
  • 反转区间的目的是让变化的幅度尽可能小，让大的数跑到较低位去嘛

 public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从后往前找到第一个递减的点 i
        while (i >= 0 && nums[i] >= nums[i + 1] ) {
            i--;
        }
        if (i >= 0) { // 说明
            // 从后往前找到第一个大于nums[i]的点
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]  )    {
                j--;
            }
            swap(nums, i, j);
            // 此时[i + 1, n] 必定是降序的， 变为升序
        }
        reverse(nums, i + 1);
    }
    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left++, right--);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }