31. Next Permutation (Medium) Google 补Facebook

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

Solution 1: O(n); O(1)

236541 （找最后一个升序36）
236541 （找3后面比3大的最小一个数）
246531 （交换3,4的位置）
241356（把4后面的6531反转）

2,3,6,5,4,1 先要知道什么是下一个排列，对于这个列子，6541是全降序，这4个数的排列已经是最后一个（对于1456这4个数来说），所以要更新这4个数的前面一个数，即3，将3替换为6541中比3大，且最小的数，即4，此时变为246531，然后将6531反转，得到最后结果241356。

Step1, from right to left, find the first number which not increase in a ascending order. In this case which is3.
Step2, here we can have two situations:

1. We cannot find the number, all the numbers increasing in a ascending order. This means this permutation is the last permutation, we need to rotate back to the first permutation. So we reverse the whole array, for example,6,5,4,3,2,1we turn it to1,2,3,4,5,6.

2. We can find the number, then the next step, we will start fromright mostto leftward, try to find the first number which is larger than3, in this case it is4.
   Then we swap3and4, the list turn to2,4,6,5,3,1.
   Last, we reverse numbers on the right of4, we finally get2,4,1,3,5,6.

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int i = nums.length - 2; //important
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--; // find the first one with index i that satisfy num[i-1] < num[i] 升序
        }

        if (i >= 0) {
//            for (int j = i + 1; j <= nums.length; j++) { //这种写法没有下面的写法好。
//                if (j == nums.length || nums[j] <= nums[i]) {
//                    swap(nums, i, j - 1);
//                    break;
//                }
//            }
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int low) {
        int high = nums.length - 1;
        while (low < high) {
            swap(nums, low, high);
            low++;
            high--;
        }
    }

Follow Up:

1.Previous Permutation 把两个<=换成>=即可。[2,7,6,4,1,3,5]

2764135 （找最后一个降序41）
2764135 （找4后面比4小的最后一个数3）这里最后指最大
2763145 （交换4，3的位置）
2763541 （把3后面的1,4,5反转）

2.大家注意下对于已经是最大数的处理方式 不一定是返回最小值 也可能是返回原值 一定要问清楚！！！我就上当了