企业官网建设流程全解析

LeetCode 31：下一个排列（Next Permutation）—— 完整题解笔记 ✅

🔗 题目链接

👉 https://leetcode.cn/problems/next-permutation/

📖 内容概要

给定一个整数数组nums，表示一个排列，要求原地修改，将其变为字典序中下一个更大的排列。
若不存在下一个更大排列，则返回最小的排列（升序）。

✅ 时间复杂度 O(n)
✅ 空间复杂度 O(1)
✅ 面试高频题

💡 解题思路（核心）

一、关键思想

• 从右往左看：
  • 如果右侧一直递增（左 < 右），说明这部分已经是最大状态
  • 只有当某个位置“变小”时，才可能变得更大

二、三步法

✅ 第一步：从右往左找第一个“降序数”

while(i>=0&&nums[i]>=nums[i+1])i--;

找到的nums[i]是：

从右往左第一个小于它右边邻居的数

含义：

• nums[i]是可以变大的最低位
• i右侧是最大后缀

✅ 第二步：找nums[i]右边最小的比它大的数

while(j>i&&nums[j]<=nums[i])j--;swap(nums,i,j);

• 在i右侧
• 找刚好比nums[i]大的最小数
• 交换

👉 保证：

• 排列变大
• 增幅最小

✅ 第三步：反转i右侧部分

reverse(nums,i+1,n-1);

• 交换后右侧仍是降序
• 反转后得到最小后缀
• 构成下一个排列

三、特殊情况

📌 举例说明（非常重要）

示例数组

nums = [1, 3, 5, 4, 2]

Step 1️⃣：找第一个降序数

从右往左：

2 < 4 < 5 > 3

找到：

i = 1 nums[i] = 3

✅ 3 是第一个“右边还有更大数”的数

Step 2️⃣：找右边最小的大数并交换

i = 1，右边是：

[5, 4, 2]

从右往左找第一个大于 3 的数：

4

交换3和4：

[1, 4, 5, 3, 2]

Step 3️⃣：反转 i 右侧部分

反转[5, 3, 2]：

[2, 3, 5]

最终结果：

[1, 4, 2, 3, 5]

✅ 这就是下一个排列

✅ 对比验证

✅ AC 代码（Java）

classSolution{publicvoidnextPermutation(int[]nums){intn=nums.length;inti=n-2;// 第一步：从右往左找第一个降序的位置while(i>=0&&nums[i]>=nums[i+1]){i--;}// 第二步：交换if(i>=0){intj=n-1;while(i<j&&nums[j]<=nums[i]){j--;}swap(nums,i,j);}// 第三步：反转reverse(nums,i+1,n-1);}privatevoidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}privatevoidreverse(int[]nums,inti,intj){while(i<j){swap(nums,i++,j--);}}}

⏱️ 复杂度分析

✅ 一句话总结

从右往左找到第一个“还能变大”的位置，把它换成右边最小的大数，再把后面变成最小后缀。

掌握这道题，就掌握了：

• 字典序排列
• 原地数组操作
• 指针边界控制