LeetCode 31. 下一个排列

约 4 分钟
文章信息 20 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 网易 虾皮 携程 LeetCode 热题 100
标签
数组 双指针 下一个更大元素问题 排列问题
目录

题目描述

✅ 31. 下一个排列

image-20230305171846186

题意分析

把数组的元素看成一个序列，所有元素的重排构成若干个排列，按字典序排好队。题目要求把 nums 变成队列里紧挨着它后面的那一个；如果它已经是队尾（整个数组非递增），就绕回队首，即变成升序的最小排列。

「紧挨着」是这道题真正的难点。比 nums 大的排列通常有很多个，要的是其中最小的那一个，所以不能随便找一个更大的排列交差；同时也不能靠枚举全部排列再排序，那是阶乘级的代价。

题面明确要求原地修改、只允许常数额外空间，并且方法没有返回值。这两条约束把「先生成再挑选」「拷贝一份排序」之类的思路全部排除，答案必然是在原数组上做有限次交换和翻转。

需要留意的边界情形：数组本身已是降序（如 [3,2,1]）时要整体变成升序；数组含重复元素（如 [1,1,5]）时，「更大」必须按严格大于理解，不能把相等的元素当成可以增大的对象；数组长度为 1 时结果就是它自己，任何写法都不能越界。

解法：寻找下降拐点并反转后缀

核心思路

为得到字典序中紧邻的下一个排列，应尽量保持左侧不变：

  1. 从右向左找到第一个 nums[i] < nums[i + 1] 的位置 i。
  2. 从右向左找到第一个严格大于 nums[i] 的元素并交换。
  3. 将 i 右侧的非递增后缀反转为升序。

若找不到 i，说明当前排列已经最大，直接反转整个数组得到最小排列。

解题步骤

  • 从 n - 2 开始向左跳过非递增部分，确定拐点 i。
  • 若 i >= 0，从末尾找到第一个 nums[j] > nums[i] 的元素并交换。
  • 反转区间 [i + 1, n - 1]。当 i = -1 时，这一步自然反转整个数组。

代码实现

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }

    for left, right := i+1, len(nums)-1; left < right; left, right = left+1, right-1 {
        nums[left], nums[right] = nums[right], nums[left]
    }
}

复杂度分析

  • 时间复杂度：$O(n)$，查找和反转都只线性扫描数组。
  • 空间复杂度：$O(1)$，在原数组上修改。

关键点总结

  • 拐点必须是最靠右且满足 nums[i] < nums[i + 1] 的位置。
  • 交换对象是后缀中大于拐点值的最小元素；非递增后缀中从右向左第一个符合条件的元素就是它。
  • 交换后的后缀仍为非递增，反转即可得到最小的升序排列。

易错点总结

  • 查找拐点时漏掉等号，重复元素会导致错误。
  • 交换时使用大于等于而非严格大于，排列可能没有变大。
  • 找不到拐点时仍尝试交换，会访问负下标。
  • 反转起点应为 i + 1，且无论是否找到拐点都要执行。

相似题目

题目 难度 考察点
556. 下一个更大元素 III 中等 同一套拐点算法作用在数字的十进制位上，额外要处理 32 位溢出
670. 最大交换 中等 只允许交换一次且求最大值，改为从右往左维护最大数字的位置
738. 单调递增的数字 中等 求不超过给定值的最大单调递增数，方向相反，需要借位并把后缀置 9
46. 全排列 中等 要求列出全部排列而非单个后继，用回溯枚举，代价是阶乘级
47. 全排列 II 中等 含重复元素的全排列去重，也可用本题算法反复迭代生成有序结果
60. 排列序列 困难 直接求第 k 个排列，用阶乘进制逐位确定，比迭代 k 次后继更快
189. 轮转数组 中等 同样依赖原地反转技巧，但用的是「三次反转」而非单段反转