LeetCode刷题笔记（31.下一个排列）

31.下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

class Solution {
    public void nextPermutation(int[] nums) {
         int minIndex = -1;
         int maxIndex = -1;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                minIndex = i;
                break;
            }
        }
        if(minIndex==-1) {
         int p1 = 0,p2 = nums.length-1;
         while(p1<p2){
             int tmp = nums[p1];
             nums[p1] = nums[p2];
             nums[p2] = tmp;
             ++p1;
             --p2;
                     }    
         return ;
        }
        for(int i=nums.length-1;i>minIndex;i--){
            if(nums[i]>nums[minIndex]){
                maxIndex = i;
                break;
            }
        }
        int tmp = nums[minIndex];
        nums[minIndex] = nums[maxIndex];
        nums[maxIndex] = tmp;
        int p1 = minIndex+1;
        int p2 = nums.length-1;
        while(p1<p2){
            tmp = nums[p1];
            nums[p1] = nums[p2];
            nums[p2] = tmp;
            ++p1;
            --p2;
        }
        
    }
}

1.我们在找下一个排序的时候，一定是让高位的小数字和低位的大数字进行交换
2.我们在找下一个排列的时候，会尽可能让高位的小数字靠右，也就是尽可能让低位的数字变大。所以我们从低位往高位找，观察有没有数字可以被比他低位的数字替换。

以[1,2,5,4,1]为例。

我们从低位往高位找，发现2可以被后面的更大的数字替换，然后我们希望被替换后的数字尽可能的小，在[5,4,1]中比2大的最小的数字为4，所以将2和4替换。
替换后的数组为[1,4,5,2,1]，然后我们将替换的数字后面数字进行从小到大的排序即可，这时候我们需要借助一个技巧，就是被替换的数字后面的数字是降序的，比如上面的样例中，我们找到2为需要被替换的数字，2后面的数字5,4,1为降序，然后在进行替换后，后面的数字仍然是降序的，5,2,1。所以我们只需要将后面的数字进行翻转即可完成排序。
最后时间复杂度为O(n) 空间复杂度为O(1) 只借助了两个指针进行翻转。