Next Permutation

题目地址：
https://leetcode.com/problems/next-permutation/description/

题目：

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

解题思路：
这道题就是首先找到第一个往上升的相邻的两个点，然后再从后面开始找第一个比相对于前面数大的数，将他们两个交换，然后因为后半段全是按照逆序排列，所以讲之前相对后一点的数和该数列最后一个数交换即可。好比2, 4, 3, 1 -> 3, 1, 2 , 4 。因为只有2和3的位置是接近的，2的排完了，下一个应该是3，但又因为全是逆序，所以将4和最后一个交换即可。

代码：

public void nextPermutation(int[] nums) {
    if(nums == null || nums.length <= 1){
        return;
    }
    int i = nums.length - 2;
    while(i >= 0 && nums[i] >= nums[i + 1]){
        i--;
    }
    if(i >= 0){
        int j = nums.length - 1;
        while(nums[j] <= nums[i]){
            j--;
        }
        swap(nums, j, i);
    }
    reverse(nums, i + 1, nums.length - 1);

}
public void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

public void reverse(int[] A, int i, int j) {
    while(i < j) swap(A, i++, j--);
}