Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 31 - 下一个排列 (Next Permutation)

Posted on Edited on In , ,
Symbols count in article: 4.4k Reading time ≈ 4 mins.
详解 LeetCode 31 题`下一个排列`的解题思路与 Go 语言实现。通过从右向左查找特殊位置并进行交换和反转，找到给定序列的下一个字典序排列。

问题描述

给定一个整数序列，找出其下一个字典序中更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

示例：

  • 1,2,3 → 1,3,2
  • 3,2,1 → 1,2,3
  • 1,1,5 → 1,5,1

解题思路

"下一个排列"的算法思想可以概括为以下几个步骤：

  1. 从右向左查找"较小数"：
    从数组的末尾开始向前扫描，找到第一个满足 nums[i-1] < nums[i] 的索引 i-1。这个 nums[i-1] 就是我们寻找的"较小数"。为什么是 nums[i-1] 呢？因为我们要尽可能地保持高位的数字不变，只在较低位进行调整，以得到字典序"下一个"更大的排列。找到这个 nums[i-1] 后，意味着从 nums[i] 开始到数组末尾的这部分是降序的（或者说是非升序的）。

  2. 处理特殊情况：已经是最大排列：
    如果在步骤 1 中没有找到这样的 i-1（也就是说，left 仍然是初始值 -1），这意味着整个数组是从大到小排列的（降序）。这种情况下，它已经是字典序最大的排列了。根据题目要求，此时应该将其变为最小的排列，也就是将整个数组反转（变为升序）。

  3. 从右向左查找"较大数"：
    如果找到了"较小数" nums[left]，接下来我们需要在 nums[left] 右边的部分（即从索引 left+1 到数组末尾）找到一个"较大数"。这个"较大数" nums[right] 必须满足 nums[right] > nums[left]，并且在所有满足条件的数中，它应该是最小的那个，但为了方便实现，我们可以从右向左找第一个大于 nums[left] 的数，这样就能保证 nums[right] 尽可能小且位置靠右，从而使得交换后对后续升序排列的影响最小。

  4. 交换"较小数"和"较大数"：
    将步骤 1 中找到的"较小数" nums[left] 与步骤 3 中找到的"较大数" nums[right] 进行交换。

  5. 反转"较小数"之后的部分：
    交换完成后，数组 nums 中索引 left 右边的部分（即从 left+1 到末尾）仍然是降序的。为了得到字典序中紧邻的下一个排列，我们需要将这部分子数组反转，使其变为升序。这样，整个数组就构成了下一个更大的排列。

举个例子 [1, 3, 2]：

  1. 从右往左，2 < 3 不满足，3 > 1，所以 nums[i-1] 是 1 (left = 0)。
  2. left 不是 -1。
  3. 在 1 的右边 [3, 2] 中，从右往左找第一个大于 1 的数，是 2 (right = 2)。
  4. 交换 nums[0] 和 nums[2]：[2, 3, 1]。
  5. 反转 nums[left+1:] 即 [3, 1] 变为 [1, 3]。最终结果是 [2, 1, 3]。

再举个例子 [4, 5, 2, 6, 3, 1]：

  1. 从右往左：1 < 3，3 < 6，6 > 2。所以 nums[i-1] 是 2 (left = 2)。
  2. left 不是 -1。
  3. 在 2 的右边 [6, 3, 1] 中，从右往左找第一个大于 2 的数：1 < 2 (否)，3 > 2 (是)。所以 nums[right] 是 3 (right = 4)。
  4. 交换 nums[left] (2) 和 nums[right] (3)：数组变为 [4, 5, 3, 6, 2, 1]。
  5. 反转 nums[left+1:] 即 [6, 2, 1]。反转后变为 [1, 2, 6]。
  6. 最终结果：[4, 5, 3, 1, 2, 6]。

为什么这个方法是正确的？（通俗解释）

您可以将寻找"下一个排列"的过程想象成给一串数字"升级"，目标是找到一个比当前数字串"大一点点"的新数字串，而且这个"大一点点"的幅度要尽可能小。

想象一下我们有一串数字，比如 [4, 5, 2, 6, 3, 1]，我们要找到比它稍微大一点点的下一个排列。

  1. 从右往左，找到第一个"可以变得更大"的数字（我们的"拐点"）

    • 我们从最右边的数字开始看。1 没法变得更大（除非前面的数字变了）。3 比 1 大，但 3,1 这个组合已经是 3 开头的最大组合了。6,3,1 也是 6 开头的最大组合。
    • 直到我们看到 2 和 6 (nums[i-1]=2, nums[i]=6)。啊哈！这里的 2 是一个"拐点"，因为 2 < 6。这意味着，如果我们把 2 换成一个比它稍微大一点的数，并且让 2 后面的数字排列得尽可能小，我们可能就能找到答案。
    • 这个"拐点"就是我们代码中的 nums[left] (即数字 2)。它左边的 [4, 5] 我们暂时不动，因为改动它们会使得数字串的"升级"幅度过大。我们希望改动尽可能靠右。
    • 特殊情况：如果一路从右到左都是降序的，比如 [6, 5, 4, 3, 2, 1]，那就说明这已经是"顶级配置"，不可能有比它更大的了。此时，它的"下一个"就是最小的排列 [1, 2, 3, 4, 5, 6]。

  2. 在"拐点"右边，找到一个比它"大一点点"的数字来替换它

    • 现在我们盯住了"拐点" 2。在它右边的 [6, 3, 1] 中，我们要找一个比 2 大，但又尽可能小的数字。
    • 6 比 2 大，3 比 2 大，1 比 2 小。在 6 和 3 中，3 是那个"大一点点"的数字。这个就是我们代码中的 nums[right]。
    • 为什么要找"大一点点"的？因为我们要的只是"下一个"排列，不是随便一个更大的排列。

  3. 交换这两个数字

    • 我们把 2 和 3 交换位置。原序列 [4, 5, 2, 6, 3, 1] 变为 [4, 5, 3, 6, 2, 1]。
    • 现在，[4, 5, 3, ...] 肯定比 [4, 5, 2, ...] 要大了。

  4. 将"拐点"之后的部分重新排列成最小的顺序

    • 交换后，序列是 [4, 5, 3, 6, 2, 1]。"拐点"之后的部分是 [6, 2, 1]。
    • 为了确保我们得到的是紧邻原序列的下一个排列（而不是随便一个更大的排列），我们需要让 [6, 2, 1] 这部分变成它能形成的最小排列。
    • 一个（大致）降序的序列（如 [6, 2, 1]）如何变成最小的排列呢？直接反转它！[6, 2, 1] 反转后变成 [1, 2, 6]。
    • 所以，最终的下一个排列就是 [4, 5, 3, 1, 2, 6]。

总结一下这个"升级"策略：

  • 找对地方升级：从右边找到第一个能让数字串"增值"的"拐点"。
  • 小幅度升级：用一个只比"拐点"大一点点的数字替换它。
  • 后续部队最小化：让"拐点"后面的数字排列成最小的顺序，确保整体"升级"幅度最小。

这样一套操作下来，就能保证我们找到的是字典序中，刚好比原来大一点点的那个排列。

代码实现

以下是优化后的 Go 语言代码实现，并附有详细注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main

// @lc code=start
func nextPermutation(nums []int) {
    n := len(nums)
    if n <= 1 {
        return // 如果数组长度小于等于1，则无需操作
    }

    // 步骤 1: 从右向左找到第一个满足 nums[i-1] < nums[i] 的 i-1
    // 这个 nums[i-1] 就是我们要找的"较小数"
    // 它的右边部分 (nums[i] 到 nums[n-1]) 是降序的
    left := -1
    for i := n - 1; i >= 1; i-- {
        if nums[i-1] < nums[i] {
            left = i - 1
            break
        }
    }

    // 步骤 2: 如果 left == -1，说明整个数组是降序的，已经是最大的排列
    // 此时，下一个排列就是最小的排列，即整个数组反转
    if left == -1 {
        reverse(nums)
        return
    }

    // 步骤 3: 从右向左找到第一个满足 nums[j] > nums[left] 的 j
    // 这个 nums[j] 就是我们要找的"较大数"
    // 因为 nums[left+1:] 是降序的，所以从右往左第一个大于 nums[left] 的数
    // 就是 nums[left+1:] 中大于 nums[left] 的最小的数
    right := -1
    for i := n - 1; i > left; i-- { // 注意这里的循环条件是 i > left
        if nums[i] > nums[left] {
            right = i
            break
        }
    }

    // 步骤 4: 交换 nums[left] 和 nums[right]
    nums[left], nums[right] = nums[right], nums[left]

    // 步骤 5: 反转 nums[left+1:] 部分，使其变为升序
    // 因为交换后，nums[left+1:] 部分仍然是降序的
    // 将其反转可以得到这部分数的最小排列
    reverse(nums[left+1:])
}

// reverse 函数用于反转一个整数切片 (原地操作)
func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}
// @lc code=end

复杂度分析

  • 时间复杂度: $O(N)$

    • 查找 left 最多需要遍历一次数组，复杂度为 $O(N)$。
    • 查找 right 最多需要遍历一次数组（从 n-1到 left+1），复杂度为 $O(N)$。
    • reverse 函数反转数组的一部分，最多反转整个数组，复杂度为 $O(N)$。
    • 因此，总的时间复杂度是 $O(N)$。

  • 空间复杂度: $O(1)$

    • 算法是在原地修改数组，只使用了几个额外的变量来存储索引，所以空间复杂度是常数级别的。

关键收获

  • 理解"下一个字典序排列"的含义是关键。目标是找到比当前排列"大一点点"的下一个排列。
  • 算法的核心在于从右边找到一个"拐点"（较小数），然后用右边一个恰好比它大的数（较大数）替换它，并重排剩余部分为最小序列。
  • 这是一个经典的数组操作问题，通过巧妙的查找和反转操作，可以在线性时间和常数空间内解决。
  • 注意边界条件，例如数组本身就是最大排列（完全降序）的情况。