image.png
    这道题的要求：

    • 我们希望下一个排列后的数比当前数大。
    • 还希望下一个排列后的数增加的幅度尽可能小（关键）

    那么怎么使增加的幅度尽可能小，需要

    1. 找到尽可能小且靠右的数（说明需要从右向左找，找到一对左小右大的数，此时i+1~n必然时下降序列）；和 找到与该数后面某个 比它大但尽可能小的数（因为i后面是下降序列，说明需要 从右向左找，找到第一个比该数大的数值） 进行交换。

      • 靠右是因为交换的位数差距不大 增加幅度小，找左小右大的数是因为 保证 右边的数和该数交换后能满足 新序列大于当前序列；右边的数可能不止一个大于该数，从中找最小是为了 满足增加幅度小。

    2. 假设这两个数为a[i]（左），a[j]（右）。即使交换了值，i+1~n的区间还是降序，数值大的在位数大的位置，那我们就将i+1~n的区间进行降序，这样就变成数值大的在位数小，降低增加幅度。

    如果没有比原始数列更大的了，说明该数列为降序的，那么直接翻转就变最小数列了。

    1. class Solution {
    2.     public void nextPermutation(int[] nums) {
    3.         int i=nums.length-2;
    4.         while(i>=0&&nums[i]>=nums[i+1]){ 
    5.             i--;
    6.         }
    7.         if(i>=0){
    8.              int j=nums.length-1;
    9.          while(j>0&&nums[i]>=nums[j]){
    10.             j--;
    11.         }
    12.         swap(nums,i,j);
    13.         }
    14.         reverse(nums,i+1);
    15.     }
    16.     public void swap(int[] nums,int i,int j){
    17.         int temp=nums[i];
    18.         nums[i]=nums[j];
    19.         nums[j]=temp;
    20.     }
    21.     public void reverse(int[] nums,int start){
    22.             int left=start;
    23.             int right=nums.length-1;
    24.             while(left<right){
    25.                 swap(nums,left,right);
    26.                 left++;
    27.                 right--;
    28.             }
    29.     }
    30. }

    这里面有个细节，就是判断大小时需要使用 ‘=’，如果两个数相同，指针还是向左移动一格，那么幅度会增加10倍。