当前位置：首页 > news >正文

【LeetCode 热题 100】31. 下一个排列

news 2025/8/27 9:08:01

Problem: 31. 下一个排列

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

这段代码旨在解决经典的 “下一个排列” (Next Permutation) 问题。问题要求重新排列一个整数数组，使其变为字典序上的下一个更大的排列。如果不存在更大的排列（即数组已经是降序排列），则将其重新排列为最小的排列（即升序排列）。这个操作必须在原地完成，只使用常数级的额外空间。

该算法是一种非常精巧的、基于观察的单次遍历解法。其核心思想是，要找到下一个更大的排列，我们需要从右向左找到第一个“破坏”降序趋势的数字，然后用一个比它稍大的数替换它，并对后面的部分进行排序以得到最小的增量。

算法的逻辑步骤可以分解为以下四步：

从右向左查找第一个“升序”对 (找到“小数”)：
- 算法从数组的倒数第二个元素 (i = n - 2) 开始向左扫描。
- 它寻找第一个满足 nums[i] < nums[i + 1] 的索引 i。
- 为什么？ 从右边看，只要 nums[i] >= nums[i+1] 持续成立，说明 [i, n-1] 这个后缀是一个降序（或非增序）序列。一个降序序列已经是它所能构成的最大排列。为了找到一个更大的排列，我们必须在更左边找到一个可以增大的“枢轴点”。这个 nums[i] 就是这个枢轴点，我们称之为“小数”。
从右向左查找第一个比“小数”大的数 (找到“大数”)：
- 在找到 i 之后，算法再从数组的最右端 (j = n - 1) 开始向左扫描。
- 它寻找第一个满足 nums[j] > nums[i] 的索引 j。
- 为什么？ 我们需要用一个比 nums[i] 大的数来替换它，以确保新的排列比旧的大。为了让这个增量尽可能小（以得到“下一个”排列），我们应该选择那个在后缀 [i+1, n-1] 中比 nums[i] 大的数里面最小的那个。由于后缀 [i+1, n-1] 是降序的，所以从右向左找到的第一个比 nums[i] 大的数 nums[j] 恰好就是这个“稍大”的数。
交换“小数”和“大数”：
- 找到 i 和 j 后，交换 nums[i] 和 nums[j] 的值。
- 效果：此时，[0, i] 这部分已经确保了新的排列比原来的大。
反转“小数”位置之后的所有数：
- 在交换之后，后缀 [i+1, n-1] 仍然保持降序。
- 为什么？ 为了得到紧邻的下一个排列，我们需要让 [i+1, n-1] 这部分变为它所能构成的最小排列。一个降序序列的最小排列就是将其变为升序。
- 因此，算法将 [i+1, n-1] 这个区间进行反转，使其变为升序。
特殊情况：
- 如果步骤1中的 while 循环结束后 i 变成了负数，这说明整个数组是完全降序的（如 [3, 2, 1]）。此时不存在更大的排列，算法会跳过步骤2和3，直接执行步骤4，反转整个数组（从索引0开始），得到最小的排列（升序）。

完整代码

class Solution {/*** 找到并原地修改数组为下一个更大的字典序排列。* @param nums 整数数组*/public void nextPermutation(int[] nums) {int n = nums.length;// 步骤 1: 从右向左查找第一个“升序”对 (nums[i] < nums[i+1])// i 是这个“小数”的索引。int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 如果 i >= 0, 说明找到了这样的“小数”，即数组不是完全降序的。if (i >= 0) {// 步骤 2: 从右向左查找第一个比 nums[i] 大的数// j 是这个“大数”的索引。int j = n - 1;while (nums[i] >= nums[j]) {j--;}// 步骤 3: 交换“小数”和“大数”swap(nums, i, j);}// 步骤 4: 反转“小数”位置之后的所有数// 如果 i < 0 (数组完全降序)，这将反转整个数组，得到最小排列。// 否则，这将使交换后的后缀变为最小排列。reverse(nums, i + 1, n - 1);}/*** 辅助函数：交换数组中两个索引位置的元素。*/private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}/*** 辅助函数：原地反转数组的指定区间 [left, right]。*/private void reverse(int[] nums, int left, int right) {while (left < right) {swap(nums, left++, right--);}}
}