《LeetCode砍怪升级系列》独特解法篇

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

• 题目列表
• • 【第1题】下一个排列
  • • 1.题目描述
    • 2.解题思路
    • 3.代码详解

LeetCode地址：https://leetcode.cn/problems/next-permutation/

1.先从右往左找到第一次降序的位置，记为 firstDonw 。
2.如果全为降序，直接reverse数组，返回。
3.否则：在从 firstDonw 这个位置右边的序列中，找到大于该位置的第一个值，记为 firstLarge。
4.之后交换 firstDonw 和 firstLarge 的值。
5.最后逆序从 firstDonw+1 开始的右边序列的值。

class Solution {
    public void nextPermutation(int[] nums) {
        //1.先从右往左找到第一次降序的位置
        //2.在从这个位置右边的序列中，找到大于该位置的第一个值
        //3.之后将右边的序列逆序
        int firstDonw = -1;
		
        for(int i = nums.length - 1; i > 0; i--){//[]
            if(nums[i - 1] < nums[i]){ 
                    firstDonw = i -1;
                    break;
            }
        }

        if(firstDonw == -1){ //全部降序，直接reverse返回
            reverse(nums,0,nums.length -1);
            return;
        }else{
            int firstLarge = -1;
            for(int i = nums.length - 1; i > firstDonw; i--){//找到firstLarge用于swap
                if(nums[firstDonw] < nums[i]){
                    firstLarge = i;
                    break;
                }
            }
            swap(nums,firstDonw,firstLarge);
            reverse(nums,firstDonw+1,nums.length-1);// reverse firstDonw右边的数组值
        }
    }

    public void swap(int nums[],int p1,int p2){
        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }

    public void reverse(int[] nums,int L,int R){ //[]
        int i = L;
        int j = R;
        while(i < j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}