一、题目描述给定整数数组nums表示一个排列。请原地将其修改为字典序更大的下一个排列。如果不存在更大的排列则将其重排为最小排列升序。只允许使用O(1) 额外空间。示例示例 1输入nums [1,2,3] 输出[1,3,2]示例 2输入nums [3,2,1] 输出[1,2,3]示例 3输入nums [1,1,5] 输出[1,5,1]二、题目本质分析这道题表面是数组操作本质是排列的字典序问题。我们从小到大列举[1,2,3]的全排列[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]可以发现一个规律越靠右的数字变化越快想要得到“下一个更大的排列”就要尽可能少地改变高位让低位变大一点点这就引出了经典解法从右往左扫描 一次交换 反转后缀三、核心思路拆解重点Step 1从右向左找到第一个「下降的位置」定义指针i从右往左扫描找到第一个满足nums[i] nums[i 1]这个nums[i]就是需要被增大的位置。如果找不到这样的i说明整个数组是非递增的已经是最大排列此时直接反转整个数组即可Step 2从右向左找到第一个比 nums[i] 大的数再从右往左扫描找到第一个nums[j] nums[i]这个nums[j]是比当前位稍大的最小数。交换nums[i]和nums[j]。Step 3反转 i1 到末尾的区间交换后i1到末尾仍然是降序排列的。为了让结果尽可能小需要将这部分反转成升序。四、举个例子关键理解以nums [1,2,3,5,4,2]为例。第一步找下降位置从右往左2 4 ✅ 4 5 ❌找到i 3nums[i] 3第二步找可交换的数从右往左找第一个大于 3 的数2 ❌ 4 ✅交换3和4[1,2,4,5,3,2]第三步反转后缀反转i1之后的区间[5,3,2] → [2,3,5]最终结果[1,2,4,2,3,5]✅ 这就是字典序的下一个排列。五、为什么这样做一定正确步骤目的找下降位保证高位改动尽可能小找稍大值保证新排列只大一点点反转后缀后缀从最大变为最小这是数学上严格成立的字典序构造方式。六、Java 代码实现class Solution { public void nextPermutation(int[] nums) { int n nums.length; // Step 1: 从右往左找第一个 nums[i] nums[i 1] int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } // Step 2: 如果找到了找可交换的位置 if (i 0) { int j n - 1; while (j i nums[j] nums[i]) { j--; } swap(nums, i, j); } // Step 3: 反转 i1 到末尾 reverse(nums, i 1, n - 1); } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void reverse(int[] nums, int left, int right) { while (left right) { swap(nums, left, right); left; right--; } } }七、复杂度分析指标数值时间复杂度O(n)空间复杂度O(1)每个元素最多被访问两次完全符合题目对原地修改的要求八、易错点总结面试高频找不到下降位时一定要反转整个数组交换后必须反转后缀否则结果不是“下一个最小”不要试图排序后缀排序是O(n log n)这里是O(n)九、总结解法特点暴力枚举超时排序不满足原地要求本题解法✅ O(n)O(1)面试标准答案一句话记忆口诀从右找降位换个大一点后缀全反转。这道题是面试中非常经典的数组 贪心 字典序综合题强烈建议熟练掌握。
LeetCode 31. 下一个排列：从直觉到算法的完整推导
一、题目描述给定整数数组nums表示一个排列。请原地将其修改为字典序更大的下一个排列。如果不存在更大的排列则将其重排为最小排列升序。只允许使用O(1) 额外空间。示例示例 1输入nums [1,2,3] 输出[1,3,2]示例 2输入nums [3,2,1] 输出[1,2,3]示例 3输入nums [1,1,5] 输出[1,5,1]二、题目本质分析这道题表面是数组操作本质是排列的字典序问题。我们从小到大列举[1,2,3]的全排列[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]可以发现一个规律越靠右的数字变化越快想要得到“下一个更大的排列”就要尽可能少地改变高位让低位变大一点点这就引出了经典解法从右往左扫描 一次交换 反转后缀三、核心思路拆解重点Step 1从右向左找到第一个「下降的位置」定义指针i从右往左扫描找到第一个满足nums[i] nums[i 1]这个nums[i]就是需要被增大的位置。如果找不到这样的i说明整个数组是非递增的已经是最大排列此时直接反转整个数组即可Step 2从右向左找到第一个比 nums[i] 大的数再从右往左扫描找到第一个nums[j] nums[i]这个nums[j]是比当前位稍大的最小数。交换nums[i]和nums[j]。Step 3反转 i1 到末尾的区间交换后i1到末尾仍然是降序排列的。为了让结果尽可能小需要将这部分反转成升序。四、举个例子关键理解以nums [1,2,3,5,4,2]为例。第一步找下降位置从右往左2 4 ✅ 4 5 ❌找到i 3nums[i] 3第二步找可交换的数从右往左找第一个大于 3 的数2 ❌ 4 ✅交换3和4[1,2,4,5,3,2]第三步反转后缀反转i1之后的区间[5,3,2] → [2,3,5]最终结果[1,2,4,2,3,5]✅ 这就是字典序的下一个排列。五、为什么这样做一定正确步骤目的找下降位保证高位改动尽可能小找稍大值保证新排列只大一点点反转后缀后缀从最大变为最小这是数学上严格成立的字典序构造方式。六、Java 代码实现class Solution { public void nextPermutation(int[] nums) { int n nums.length; // Step 1: 从右往左找第一个 nums[i] nums[i 1] int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } // Step 2: 如果找到了找可交换的位置 if (i 0) { int j n - 1; while (j i nums[j] nums[i]) { j--; } swap(nums, i, j); } // Step 3: 反转 i1 到末尾 reverse(nums, i 1, n - 1); } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void reverse(int[] nums, int left, int right) { while (left right) { swap(nums, left, right); left; right--; } } }七、复杂度分析指标数值时间复杂度O(n)空间复杂度O(1)每个元素最多被访问两次完全符合题目对原地修改的要求八、易错点总结面试高频找不到下降位时一定要反转整个数组交换后必须反转后缀否则结果不是“下一个最小”不要试图排序后缀排序是O(n log n)这里是O(n)九、总结解法特点暴力枚举超时排序不满足原地要求本题解法✅ O(n)O(1)面试标准答案一句话记忆口诀从右找降位换个大一点后缀全反转。这道题是面试中非常经典的数组 贪心 字典序综合题强烈建议熟练掌握。
