31. Next Permutation

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

思路：从网上抄的

遇到这类概念比较抽象的题目，写几个例子通常会帮助理解问题的规律：

7 2 5 2 3 1
7 2 5 3 1 2
7 2 5 3 2 1
7 3 1 2 2 5

1. 从低位向高位（从右向左）找第一个递减的数：s[i]<s[i+1]。如果不存在，则表明该permutation已经最大，next permutation为当前序列的逆序。
2. 在s[i+1:n-1]中找一个j，使s[j]>s[i]>=s[j+1]，swap(s[i], s[j])
3. 将s[i+1:n-1]排序，从低位到高位单调递减。

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums==null||nums.length<2) return;

        //step 1 find larger one
        int p = 0;
        for(int i=nums.length-2;i>=0;i--){
            if (nums[i]<nums[i+1]){
                p = i;
                break;
            }
        }

        //step 2 find the smallest > p on the right
        int q = 0;
        for(int j=nums.length-1;j>p;j--){
            if (nums[j]>nums[p]){
                q = j;
                break;
            }
        }

        //step 3 switch entire row if it has been the largest number
        if (p==0&&q==0){
            reverse(nums,0,nums.length-1);
            return;
        }

        //step 4 switch two values
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;

        //step 5 reverse the last part
        if(p<nums.length-1){
            reverse(nums,p+1,nums.length-1);
        }
    }

    public void reverse(int[] nums,int left, int right){
        while(left<right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
        return;
    }
}