二刷 LeetCode：75. 颜色分类 31. 下一个排列 复盘笔记
目录
一、75. 颜色分类（荷兰国旗问题）
题目回顾
思路复盘
核心思想
Python 代码实现
易错点 & 二刷心得
二、31. 下一个排列
题目回顾
思路复盘
核心步骤
Python 代码实现
易错点 & 二刷心得
三、两道题的共性总结 & 二刷收获
这两道题是数组 / 排序专题的经典中等题，也是面试中常考的 “原地操作” 类型，非常适合用来巩固双指针和贪心思想。二刷时我们重点拆解核心思路、优化写法，并总结通用解题模板。
一、75. 颜色分类（荷兰国旗问题）
题目回顾
给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。
思路复盘
这道题的最优解是三指针法（荷兰国旗问题），时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)，一次遍历完成排序。
核心思想
定义三个指针：
p0：指向 0 的右边界，初始为 0p2：指向 2 的左边界，初始为len(nums)-1curr：当前遍历的元素指针，初始为 0
遍历规则：
- 当
nums[curr] == 0：和nums[p0]交换，p0++、curr++ - 当
nums[curr] == 2：和nums[p2]交换，p2--（注意curr不增加，因为交换来的元素需要再判断） - 当
nums[curr] == 1：直接curr++
Python 代码实现
python
运行
def sortColors(nums: list[int]) -> None: p0 = curr = 0 p2 = len(nums) - 1 while curr <= p2: if nums[curr] == 0: nums[p0], nums[curr] = nums[curr], nums[p0] p0 += 1 curr += 1 elif nums[curr] == 2: nums[curr], nums[p2] = nums[p2], nums[curr] p2 -= 1 else: curr += 1易错点 & 二刷心得
- 边界控制：循环条件必须是
curr <= p2，因为p2左边的元素还未处理完。 - 交换 2 时的指针处理：交换
curr和p2后，curr不能自增，因为新交换来的元素可能是 0 或 2，需要再次判断。 - 原地修改：题目要求不使用额外空间，所以不能用计数排序后再重写数组，三指针法是最优解。
二、31. 下一个排列
题目回顾
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。
思路复盘
这道题的核心是贪心思想，找到 “下一个更大” 的排列，关键步骤可以总结为 “找、换、反转” 三步。
核心步骤
- 找：从后往前找第一个
nums[i] < nums[i+1]的位置i，这个位置是 “下降点”，后面的元素是降序的。 - 换：从后往前找第一个比
nums[i]大的元素nums[j]，交换nums[i]和nums[j]。 - 反转：将
i之后的元素反转，使其变为升序，这样得到的就是比原排列大的最小排列。
Python 代码实现
python
运行
def nextPermutation(nums: list[int]) -> None: n = len(nums) # 步骤1：找下降点 i = n - 2 while i >= 0 and nums[i] >= nums[i+1]: i -= 1 # 步骤2：如果不是最后一个排列，找比nums[i]大的最小数并交换 if i >= 0: j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] # 步骤3：反转i之后的部分 left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1易错点 & 二刷心得
- 下降点的理解：如果整个数组是降序的，说明没有下一个排列，直接反转整个数组即可。
- 交换后反转的必要性：交换
nums[i]和nums[j]后，i之后的部分仍然是降序的，反转后才能变成升序，得到最小的更大排列。 - 边界处理：当
i < 0时，说明数组是降序的，直接反转整个数组即可，无需额外处理。
三、两道题的共性总结 & 二刷收获
- 原地操作的核心思想：两道题都要求在不使用额外空间的情况下修改数组，核心都是通过双指针 / 多指针实现元素的交换和重排。
- 贪心算法的应用：
- 颜色分类：通过指针划分区域，一次遍历完成分类，局部最优（每次把元素放到正确位置）得到全局最优。
- 下一个排列：通过 “找下降点、交换、反转” 三步，找到字典序下的最小更大排列，同样是贪心思想的体现。
- 面试高频考点：
- 颜色分类：重点考察三指针法和荷兰国旗问题，是多指针思想的经典应用。
- 下一个排列：重点考察对排列字典序的理解和原地修改的技巧，面试中常被追问时间复杂度和空间复杂度优化。