下一个排列

更新: 7/4/2026 字数: 0 字时长: 0 分钟

题目描述

给定一个整数数组 nums，找出它按字典序排列的下一个排列。

「下一个排列」是指：把数字重新排列后，得到的所有排列中，字典序恰好比当前大一位的那个。
如果当前排列已经是最大（数字整体降序），则它没有更大的排列，此时要返回最小排列（整体升序）。
必须原地修改，只允许使用常数级额外空间。

例如：[1,2,3] → [1,3,2]；[3,2,1] → [1,2,3]；[1,1,5] → [1,5,1]。

下一个排列的直观含义：在所有排列的字典序序列中，找到当前排列的“下一格”

思路拆解

先想暴力解法

最直接的想法：生成所有排列，按字典序排好，再找到当前排列的下一个。

点击展开暴力解法（O(n·n!)，仅供理解）

function nextPermutationBrute(nums) {
  // 1) 生成全排列
  const perms = []
  const used = new Array(nums.length).fill(false)
  const path = []
  const dfs = () => {
    if (path.length === nums.length) { perms.push([...path]); return }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true; path.push(nums[i])
      dfs()
      path.pop(); used[i] = false
    }
  }
  dfs()
  // 2) 按字典序排序 + 去重后，定位当前排列的下一个
  perms.sort((a, b) => a.join(',') < b.join(',') ? -1 : 1)
  const key = nums.join(',')
  for (let k = 0; k < perms.length; k++) {
    if (perms[k].join(',') === key) {
      const next = perms[(k + 1) % perms.length] // 越界则回到最小
      for (let t = 0; t < nums.length; t++) nums[t] = next[t]
      return nums
    }
  }
}

排列有个，排序与生成都极其昂贵，只能应付极小规模，无法接受。

推导最优解法：三步法

关键洞察：字典序的大小由从左到右第一个能变大的位置决定。为了让排列只变大一点点，我们要尽量在靠右的位置做改动。

观察一个降序后缀的性质：一段完全降序的序列已经是它自己所有排列中最大的，无法再变大。所以要变大，必须找到降序后缀左边那一位——它才是可以被抬高的“突破口”。

由此得到经典三步法：

找低谷：从右向左找到第一个满足的位置 i（记作 pivot）。它右边是一段降序。若找不到，说明整体降序、已是最大排列。
找替换：从右向左找到第一个比大的元素，交换 a[i] 与 a[j]。因为右侧是降序，从右找到的第一个更大值，正好是“刚好比低谷大的最小值”，交换后整体只增大了最小的幅度。
反转后缀：交换后 i+1..n-1 仍是降序（最大），把它反转为升序（最小），这样后缀取到最小，整体就成了“恰好大一点”的下一个排列。

核心思路

低谷右侧永远是降序。抬高低谷位（用右侧刚好更大的最小值替换），再把后缀“压”到最小（反转成升序），就得到严格大于当前、且增幅最小的排列。

三步法图解：① 从右找低谷 i；② 从右找到刚好更大的 j 并交换；③ 反转 i 之后的后缀

动画演示

下面用样例 [1, 5, 8, 4, 7, 6, 5, 3, 1] 完整演示三步法。点击「下一步 / 自动播放」观察低谷 i、替换 j、反转区间的变化：

三步法 · 下一个排列演示

样例输入：[1, 5, 8, 4, 7, 6, 5, 3, 1]

当前阶段：准备

低谷 i扫描指针替换 j反转区间

目标：找出字典序恰好比当前排列大的下一个排列。三步法：找低谷 → 找替换 → 反转后缀。

步骤 0 / 13

完整代码

function nextPermutation(nums) {
  const n = nums.length
  // 步骤①找低谷：从右向左找第一个 nums[i] < nums[i+1]
  let i = n - 2
  while (i >= 0 && nums[i] >= nums[i + 1]) i--

  if (i >= 0) {
    // 步骤②找替换：从右向左找第一个 > nums[i] 的数
    let j = n - 1
    while (j > i && nums[j] <= nums[i]) j--
    ;[nums[i], nums[j]] = [nums[j], nums[i]]   // 交换低谷与替换值
  }

  // 步骤③反转后缀 i+1..n-1（降序 → 升序，取到最小）
  let l = i + 1, r = n - 1
  while (l < r) {
    ;[nums[l], nums[r]] = [nums[r], nums[l]]
    l++; r--
  }
  return nums
}

易错点

交换/反转这两行前建议加分号 ;，避免 JS 自动分号插入（ASI）把上一行末尾与 [...] = [...] 解构语句连成一体导致解析错误。

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举全排列			生成并排序所有排列，不可用
三步法（最优）			至多三次线性扫描，原地交换与反转

三步法的每一步都是从一端到另一端的线性扫描或反转，总操作数与成正比；除若干指针外不使用额外空间，因此空间为。

边界与易错点

已是最大排列：数组整体降序（如 [3,2,1]）时找不到低谷，i = -1。此时步骤③会反转整个数组 0..n-1，直接得到最小排列 [1,2,3]，逻辑天然覆盖，无需特判。
反转不能漏：只交换 i 与 j 而忘记反转后缀，会得到一个比目标大的排列（后缀还是降序=偏大），结果错误。
步骤②的方向：必须从右向左找第一个大于 nums[i] 的数。因为右侧是降序，这样找到的是“刚好更大的最小值”，才能保证增幅最小。
相等元素：条件用 nums[i] >= nums[i+1] 和 nums[j] <= nums[i]（含等号），保证对含重复数字的排列同样正确，如 [1,1,5] → [1,5,1]。
单元素/空数组：n <= 1 时循环不执行，数组保持不变，安全。
原地修改：题目要求原地、常数空间，切勿新建数组返回。

下一个排列 ​

题目描述 ​

思路拆解 ​

先想暴力解法 ​

推导最优解法：三步法 ​

动画演示 ​

完整代码 ​

复杂度分析 ​

边界与易错点 ​