1、前言

题目描述

2、思路

这道题比较难以理解，如果能够暴力的话，其实用全排列的思路可以一个个比较出来。但是全排列太暴力了，所以可以使用全排列的思路画图理解代码为什么要这么写。

画递归树理解

1）从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
2）在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3）将 A[i] 与 A[k] 交换
4）可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
5）如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

3、代码

class Solution {

    // 1 4 3 2 0
    // 2 0 1 3 4
    // 画全排列的图来理解
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1){
            return;
        }
        int n = nums.length;
        int i = n - 2;
        // 从后往前，找到升序中第一个打破的
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }

        // 找不到说明原数组从后往前就是升序，那么从前往后就是降序，数组就是最大的，反转一下就行
        if(i < 0){
            reverse(nums, 0, n - 1);
        }else{
            int j = n - 1;
            // 从后往前，找到比 i 位置大的数中最小的那个
            while(i < j && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
            // 然后把 i + 1 位置后的数都 reverse 一下
            reverse(nums, i + 1, n - 1);
        }
    }

    private void reverse(int[] nums, int start, int end){
        while(start <= end){
            swap(nums, start++, end--);
        }
    }

    private void swap(int[] nums, int i, int i1) {
        int tmp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = tmp;
    }
}

4、参考资料

https://www.bilibili.com/video/BV1Rz4y1Z7hx?spm_id_from=333.337.search-card.all.click