Problem: 31. 下一个排列

整体思路

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

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

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

1. 从右向左查找第一个“升序”对 (找到“小数”)：

   • 算法从数组的倒数第二个元素 (i = n - 2) 开始向左扫描。
   • 它寻找第一个满足 nums[i] < nums[i + 1] 的索引 i。
   • 为什么？ 从右边看，只要 nums[i] >= nums[i+1] 持续成立，说明 [i, n-1] 这个后缀是一个降序（或非增序）序列。一个降序序列已经是它所能构成的最大排列。为了找到一个更大的排列，我们必须在更左边找到一个可以增大的“枢轴点”。这个 nums[i] 就是这个枢轴点，我们称之为“小数”。

2. 从右向左查找第一个比“小数”大的数 (找到“大数”)：

   • 在找到 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] 恰好就是这个“稍大”的数。

3. 交换“小数”和“大数”：

   • 找到 i 和 j 后，交换 nums[i] 和 nums[j] 的值。
   • 效果：此时，[0, i] 这部分已经确保了新的排列比原来的大。

4. 反转“小数”位置之后的所有数：

   • 在交换之后，后缀 [i+1, n-1] 仍然保持降序。
   • 为什么？ 为了得到紧邻的下一个排列，我们需要让 [i+1, n-1] 这部分变为它所能构成的最小排列。一个降序序列的最小排列就是将其变为升序。
   • 因此，算法将 [i+1, n-1] 这个区间进行反转，使其变为升序。

5. 特殊情况：

   • 如果步骤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--);}}
}

时空复杂度

时间复杂度：O(N)

1. 查找 i：第一个 while 循环最多扫描整个数组一次。在最坏情况下，时间复杂度为 O(N)。
2. 查找 j：第二个 while 循环最多扫描整个数组一次。在最坏情况下，时间复杂度为 O(N)。
3. 交换：swap 操作是 O(1)。
4. 反转：reverse 函数最多需要遍历 N/2 次交换，其操作的元素数量与 N 呈线性关系。在最坏情况下，时间复杂度为 O(N)。

综合分析：
整个算法由几次独立的、不嵌套的线性扫描组成。总的时间复杂度是 O(N) + O(N) + O(N) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：该算法没有创建任何与输入规模 N 成比例的新的数据结构。
2. 辅助变量：只使用了 n, i, j, t, left, right 等几个固定数量的整型变量。

综合分析：
算法的所有操作都是在原数组上进行的（in-place），所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。

参考灵神