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.

Example

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

Solution

可以知道最后一个permutation必然是从左往右递减的。next permutation一定是逼近这个趋势。
于是首先从右往左找第一个打破这个规律的点，即第一个比后面一个数小的点，index记为firstSmall。next permutation一定是把firstSmall上的点换成比现在这个点大的点。
于是再从右往左找比firstSmall上的点大的最小的点，即从右往左碰到的第一个大于firstSmall的点，index记为firstBig。将firstSmall和firstBig swap。
至此，firstSmall上的点已经搞定。现在firstSmall以后的点仍然呈递减趋势，把他们reverse呈递增趋势之后就是next permutation。

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

        int firstSmall = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                firstSmall = i;
                break;
            }
        }
        if (firstSmall == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }

        int firstBig = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] > nums[firstSmall]) {
                firstBig = i;
                break;
            }
        }

        swap(nums, firstSmall, firstBig);
        reverse(nums, firstSmall+1, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}