31. 下一个排列 (opens new window)

1.排序

解题关键在于如何理解字典序的下一个序列。具体来说分为两个步骤：

• 从后向前遍历，找到连续降序子数组的左边界left。此时left-1位置即为需要交换的位置，找到【left，nums.length-1】区间内比left-1元素大的最小的元素，并与left-1位置交换。
• 交换后将区间【left，nums.length-1】内的元素升序排列。

class Solution {
    public void nextPermutation(int[] nums) {
        int index=-1;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                index=i;
                break;
            }
        }
        if(index==-1){
            Arrays.sort(nums);
            return;
        }
        int minmax=Integer.MAX_VALUE,minindex=index;
        for(int i=index;i<nums.length;i++){
            if(nums[i]>nums[index]){
                if(nums[i]<minmax){
                    minmax=nums[i];
                    minindex=i;
                }
            }
        }
        int temp=nums[minindex];
        nums[minindex]=nums[index];
        nums[index]=temp;
        Arrays.sort(nums,index+1,nums.length);
    }
}

2.优化

利用区间【left，nums.length-1】的元素本身就是降序这一性质：

• 查找交换元素时，只需要从后向前找到第一个比left-1大的元素
• 升序排序直接将【left，nums.length-1】翻转倒置。复杂度O(n)