Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

一刷
题解：
正常倒序应该是654321，假如652431，则2为inversion，并且next permutation应该为653124。

方法是从后向前找inversion，找到第一个inversion，如上例中，然后继续从后向前判断，假如从数组尾部到inversion元素 2 间有数字大于2， 则swap 2和这个数字，由于swap之后依然是倒序，在inversion之后的元素，掉转倒序为顺序

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length < 2) return;
        int len = nums.length;
        for(int i = len-2; i>=0; i--){
            if(nums[i] < nums[i+1]){//i is the inversion
            //find the behind element which is bigger than the inversion
                int indices = findHiger(nums, i+1, nums[i]);
            //swap
            swap(nums, i, indices);
            reverse(nums, i+1, len-1); 
            return;
            }
        }
        //not find the inversion
        reverse(nums, 0, len-1);
    }
    
    private int findHiger(int[] nums, int start, int target){
        for(int i=nums.length-1; i>=start; i--){
            if(nums[i] > target) return i;
        }
        return start;
    }
    
    private void swap(int[] nums, int i, int j){
        if(i==j) return;
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start, int end){
        while(start<end){
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}