🌕 🌗 31. 下一个排列

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    public void nextPermutation(int[] nums) {
        // 思路：
        // 画图，分情况讨论
        // 固定右节点 right ，往左找第一个比它大或等于的数 left
        // 1) [left] >= 0 && [left] < [right] ==> swap(left, right) && swap [left + 1, right]
        // 3) [left] < 0 ==> swap[left + 1, right]
        int len = nums.length;
        int right = len - 1;
        int left = right - 1;
        while(left >= 0) {
            while(left >= 0 && nums[left] >= nums[left + 1]) {
                left --;
            }
            // 情况 3) 判断
            if(left < 0) {
                // 一直降序，返回最小字典序
                mySol(nums, 0, len - 1);
                return;
            }
            // left >= 0
            // 情况 1) 判断
            if(nums[left] < nums[left + 1]) {
                // 需要找一个比 left 次大的数
                int k = right;
                while(nums[k] <= nums[left]) {
                    k --;
                }
                // [k] > [left] 
                swap(nums, left, k);
                mySol(nums, left + 1, right);
                return;
            }
        } 
    }

    private void mySol(int[] nums, int left, int right) {
        int i = left;
        int j = right;
        while(i < j) {
            swap(nums, i, j);
            i ++;
            j --;
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出