京公网安备11010502063487号给定一个整数数组，把它原地改成字典序里的下一个更大的排列；如果已经是最大的排列，就改成最小的（升序）。做法是四步：从右往左找第一个升序对 nums[i] < nums[i+1]；再从右往左找第一个比 nums[i] 大的数 nums[j]；交换二者；最后把 i 之后的部分翻转成升序。这道题的每一步都有理由，少一步就是错的。本文用真实数据展示漏掉最后一步的后果，用重复调用 solve 的方式验证它确实按字典序遍历了所有排列，给出五种语言的实现，并把四步过程做成分步演示。
完整题目见官方页面（链接在文末）。数组里可以有重复的值，这时"不同的排列"要按去重之后的算。基准解用 itertools.permutations 列出所有排列，去重、排序，取当前排列的下一个（最后一个回到第一个），是与四步法完全不同的写法。一共 14 组用例，覆盖：官方示例、单个元素、已是最大排列、含重复值、长度 2、全部相同：
输入 [[1,2,3]] 输出 [1,3,2] 输入 [[3,2,1]] 输出 [1,2,3] 输入 [[1,1,5]] 输出 [1,5,1] 输入 [[1]] 输出 [1] 输入 [[1,3,2]] 输出 [2,1,3] 输入 [[2,3,1]] 输出 [3,1,2]
前三步只是找到"要动的位置"并把它换成刚好更大的数，第四步才让后面的部分变到最小。交换之后，i 后面仍然是降序（最大排列），如果不翻转，得到的虽然是一个更大的排列，却不是"下一个"，中间跳过了很多排列。下面是漏掉翻转的真实结果：
# 交换之后没有翻转后缀的写法 [1, 2, 3]: 不翻转后缀 -> [1, 3, 2] solve -> [1, 3, 2] 暴力 -> [1, 3, 2] [1, 3, 2]: 不翻转后缀 -> [2, 3, 1] solve -> [2, 1, 3] 暴力 -> [2, 1, 3] [1, 2, 3, 6, 5, 4]: 不翻转后缀 -> [1, 2, 4, 6, 5, 3] solve -> [1, 2, 4, 3, 5, 6] 暴力 -> [1, 2, 4, 3, 5, 6] [5, 4, 7, 5, 3, 2]: 不翻转后缀 -> [5, 5, 7, 4, 3, 2] solve -> [5, 5, 2, 3, 4, 7] 暴力 -> [5, 5, 2, 3, 4, 7]
[1, 3, 2] 交换后是 [2, 3, 1]，但真正的下一个排列是 [2, 1, 3]。[1, 2, 3] 那一行两种写法碰巧相同，因为交换之后的后缀只有一个元素，翻转与否没有区别，所以这个错误在最短的例子上是看不出来的。
第一步，从右往左找第一个 nums[i] < nums[i+1]：它右边的部分是降序，说明那一段已经是它自己的最大排列，动它没有用，必须动 i。第二步，在右边降序的部分里，从右往左找第一个比 nums[i] 大的数，它是"刚好比 nums[i] 大一点"的那个。第三步交换。第四步把右边翻转：交换后右边仍是降序，翻转后变成升序，也就是这一段的最小排列。如果第一步找不到 i（整个数组是降序），就直接翻转整个数组，得到最小排列。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: # 1) 从右往左找第一个"升序对" nums[i] < nums[i+1] i -= 1 if i >= 0: j = n - 1 while nums[j] <= nums[i]: # 2) 从右往左找第一个比 nums[i] 大的数 j -= 1 nums[i], nums[j] = nums[j], nums[i] # 3) 交换 l, r = i + 1, n - 1 while l < r: # 4) 把 i 之后的部分翻转成升序（i = -1 时就是整个数组） nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 return nums
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3]] → [1,3,2] [[3,2,1]] → [1,2,3] [[1,1,5]] → [1,5,1] [[1]] → [1] [[1,3,2]] → [2,1,3] [[2,3,1]] → [3,1,2]
Java · 解法代码class Solution { public void nextPermutation(int[] nums) { int n = nums.length; int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 1) 从右往左找第一个"升序对" nums[i] < nums[i+1] if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) j--; // 2) 从右往左找第一个比 nums[i] 大的数 int t = nums[i]; nums[i] = nums[j]; nums[j] = t; // 3) 交换 } for (int l = i + 1, r = n - 1; l < r; l++, r--) { // 4) 把 i 之后的部分翻转成升序 int t = nums[l]; nums[l] = nums[r]; nums[r] = t; } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3]] → [1,3,2] [[3,2,1]] → [1,2,3] [[1,1,5]] → [1,5,1] [[1]] → [1] [[1,3,2]] → [2,1,3] [[2,3,1]] → [3,1,2]
Go · 解法代码func nextPermutation(nums []int) { n := len(nums) i := n - 2 for i >= 0 && nums[i] >= nums[i+1] { // 1) 从右往左找第一个"升序对" nums[i] < nums[i+1] i-- } if i >= 0 { j := n - 1 for nums[j] <= nums[i] { // 2) 从右往左找第一个比 nums[i] 大的数 j-- } nums[i], nums[j] = nums[j], nums[i] // 3) 交换 } for l, r := i+1, n-1; l < r; l, r = l+1, r-1 { // 4) 把 i 之后的部分翻转成升序 nums[l], nums[r] = nums[r], nums[l] } }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3]] → [1,3,2] [[3,2,1]] → [1,2,3] [[1,1,5]] → [1,5,1] [[1]] → [1] [[1,3,2]] → [2,1,3] [[2,3,1]] → [3,1,2]
JavaScript · 解法代码function nextPermutation(nums) { const n = nums.length; let i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 1) 从右往左找第一个"升序对" nums[i] < nums[i+1] if (i >= 0) { let j = n - 1; while (nums[j] <= nums[i]) j--; // 2) 从右往左找第一个比 nums[i] 大的数 [nums[i], nums[j]] = [nums[j], nums[i]]; // 3) 交换 } for (let l = i + 1, r = n - 1; l < r; l++, r--) { // 4) 把 i 之后的部分翻转成升序 [nums[l], nums[r]] = [nums[r], nums[l]]; } }
$ node run.js < cases.jsonl [[1,2,3]] → [1,3,2] [[3,2,1]] → [1,2,3] [[1,1,5]] → [1,5,1] [[1]] → [1] [[1,3,2]] → [2,1,3] [[2,3,1]] → [3,1,2]
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 1) 从右往左找第一个"升序对" nums[i] < nums[i+1] if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) j--; // 2) 从右往左找第一个比 nums[i] 大的数 swap(nums[i], nums[j]); // 3) 交换 } reverse(nums.begin() + i + 1, nums.end()); // 4) 把 i 之后的部分翻转成升序 } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3]] → [1,3,2] [[3,2,1]] → [1,2,3] [[1,1,5]] → [1,5,1] [[1]] → [1] [[1,3,2]] → [2,1,3] [[2,3,1]] → [3,1,2]
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
除了和暴力解对拍，还可以做一个更强的检查：从最小的排列出发，反复调用 solve，直到回到起点，看看一共走了几步、每一步是否都比前一步大：
从最小的排列出发，反复调用 solve，直到回到起点，统计一共走了多少步： [1, 2, 3, 4]: 24 个不同的排列，全部严格递增（字典序）=True，不同排列数 24 [1, 2, 3, 4, 5, 6, 7, 8]: 40320 个不同的排列，全部严格递增（字典序）=True，不同排列数 40320 [1, 1, 2, 2]: 6 个不同的排列，全部严格递增（字典序）=True，不同排列数 6 [1, 1, 2, 2, 3, 3]: 90 个不同的排列，全部严格递增（字典序）=True，不同排列数 90 [1, 2, 2, 3, 3, 3]: 60 个不同的排列，全部严格递增（字典序）=True，不同排列数 60
[1, 2, 3, 4] 走了 24 步，正好是 4!；八个不同数字走了 40320 步，正好是 8!，每一步都严格递增，没有重复也没有遗漏。有重复值时，走过的步数等于不同排列的个数，例如 [1, 1, 2, 2, 3, 3] 是 90，[1, 2, 2, 3, 3, 3] 是 60，都和 itertools.permutations 去重后的个数一致。
Python 版本另外和暴力解做了随机对拍，长度 1 到 7，取值 0 到 4，重复值很多：
随机对拍 10000 组（长度 1 到 7、取值 0 到 4 的随机数组（重复值很多）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。这道题每次调用是线性的，所以没有做规模对比实验。
下面的演示用 [1, 2, 7, 4, 3, 1]。从右往左，3 ≥ 1、4 ≥ 3、7 ≥ 4 都是降序，i 一直左移，到 nums[1] = 2 < 7 停下；右边的 [7, 4, 3, 1] 是降序，说明已经是最大排列，动它没有用。从右往左找第一个比 2 大的数是 3，交换后得到 [1, 3, 7, 4, 2, 1]；再把 i 之后的部分翻转成升序，得到 [1, 3, 1, 2, 4, 7]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。