题目描述
思路解析动画文字版
记牢这一句:排序后,锚点 a 盯住当前组的最小值。b - a ≤ k 就归本组,b - a > k 就另起一组。贪心之所以对,是因为排好序后,每一组尽量往右多装、直到差要超过 k 才切,组数一定最少。下面从头扫一遍。
原始输入 · 还没排序：先看原始输入,8 个数乱序排列。整个贪心都建立在有序之上,因为只有排好序,当前组的最小值才恒等于组里第一个进来的数。所以第一步永远是把 nums 从小到大排好。
排序后 · 从小到大排好：排好序后变成 1、2、3、6、7、8、11、12。现在最左边的 1 是全局最小,也是第一组的最小值。接下来右指针从左往右一个一个走,拿每个数和当前组的锚点比,决定它是留在本组还是另起一组。
扫描规则 · 锚点盯住当前组最小值：开扫之前把规则钉死。紫色是正在看的数 b,下方那个标记 a 是当前组的锚点,也就是本组最小值。每一步只做一件事:算 b - a,如果不超过 2 就并进这一组,如果超过 2 就在 b 这里切一刀、另起一组。锚点从最左的 1 起步,第一组先开着。
第 1 个数 1 · 直接开第 1 组：扫描从最左边开始。第一个数 1 无处可比,它自己就得开一组,并且当仁不让地成为这一组的锚点 a,也就是这一组的最小值。后面所有数,都要拿来和它算差。
归入第 1 组 · 1：把 1 收进第 1 组,这一组现在只有它一个,锚点也是它。继续往右看下一个数。
看 2 · 算 2 - 1 = 1：右指针走到 2。当前这一组的锚点是 1,算一下 2 减 1 等于 1。这个差 1 不超过 2,说明 2 和本组最小值挨得够近,可以安心并进来。
并入本组 · 2：把 2 并进当前组,本组现在是 [1, 2]。注意锚点 a 依然是组里最小的 1,没有变,后面的数还是拿来和它比。分组数保持 1。
看 3 · 算 3 - 1 = 2：右指针走到 3。当前这一组的锚点是 1,算一下 3 减 1 等于 2。这个差 2 不超过 2,说明 3 和本组最小值挨得够近,可以安心并进来。
并入本组 · 3：把 3 并进当前组,本组现在是 [1, 2, 3]。注意锚点 a 依然是组里最小的 1,没有变,后面的数还是拿来和它比。分组数保持 1。
看 6 · 算 6 - 1 = 5：右指针走到 6。当前这一组的锚点是 1,算一下 6 减 1 等于 5。这个差 5 已经大于 2,说明 6 和本组最小值拉得太开,再塞进来这一组的最大差就要爆 2。它进不了这一组。
另起一组 · 6 当新锚点,分组数 = 2：于是在这里切一刀。前面那组 [1, 2, 3] 就此封口,它内部最大差是 2,稳稳不超过 2。6 成为新一组的第一个数、也是新锚点,分组数从 1 涨到 2。
看 7 · 算 7 - 6 = 1：右指针走到 7。当前这一组的锚点是 6,算一下 7 减 6 等于 1。这个差 1 不超过 2,说明 7 和本组最小值挨得够近,可以安心并进来。
并入本组 · 7：把 7 并进当前组,本组现在是 [6, 7]。注意锚点 a 依然是组里最小的 6,没有变,后面的数还是拿来和它比。分组数保持 2。
看 8 · 算 8 - 6 = 2：右指针走到 8。当前这一组的锚点是 6,算一下 8 减 6 等于 2。这个差 2 不超过 2,说明 8 和本组最小值挨得够近,可以安心并进来。
并入本组 · 8：把 8 并进当前组,本组现在是 [6, 7, 8]。注意锚点 a 依然是组里最小的 6,没有变,后面的数还是拿来和它比。分组数保持 2。
看 11 · 算 11 - 6 = 5：右指针走到 11。当前这一组的锚点是 6,算一下 11 减 6 等于 5。这个差 5 已经大于 2,说明 11 和本组最小值拉得太开,再塞进来这一组的最大差就要爆 2。它进不了这一组。
另起一组 · 11 当新锚点,分组数 = 3：于是在这里切一刀。前面那组 [6, 7, 8] 就此封口,它内部最大差是 2,稳稳不超过 2。11 成为新一组的第一个数、也是新锚点,分组数从 2 涨到 3。
看 12 · 算 12 - 11 = 1：右指针走到 12。当前这一组的锚点是 11,算一下 12 减 11 等于 1。这个差 1 不超过 2,说明 12 和本组最小值挨得够近,可以安心并进来。
并入本组 · 12：把 12 并进当前组,本组现在是 [11, 12]。注意锚点 a 依然是组里最小的 11,没有变,后面的数还是拿来和它比。分组数保持 3。
回放 · 三组成型：扫完了,回放一遍。整条序列被切成三段:[1, 2, 3]、[6, 7, 8]、[11, 12]。相邻两段之间,正是那两处 b - a 大于 2 的地方切开的。绿一段、蓝一段、绿一段,颜色只为让你看清分界,一共 3 组。
验差 · 每组最大差都 ≤ 2：再逐组核对一遍最大差。第一组 3 减 1 等于 2,第二组 8 减 6 等于 2,第三组 12 减 11 等于 1,三组全都不超过 2,完全合规。而且你没法再省:每一刀都是被逼着切的,少切一刀就一定有组会爆 2。所以最少划分数就是 3。
边界想清:单个数一组、差正好等于 k 仍同组、全相等且 k=0 也能并成一组。
面试重点:子序列不要求连续引出排序、锚点贪心分组、交换论证证最优、时间 O(n log n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def partitionArray(self, nums: List[int], k: int) -> int: nums.sort() ans, a = 1, nums[0] for b in nums: if b - a > k: a = b ans += 1 return ans复杂度
- 时间：O(n log n)，瓶颈在排序,n 个数排序是 O(n log n)。排完之后只从左到右线性扫一遍,每个数做常数次比较和更新,是 O(n),整体被排序主导,合起来 O(n log n)
- 空间：O(1) 到 O(n)，算法本身只用 ans 和锚点 a 两个变量,辅助空间 O(1)。若把排序开销计入:C plus plus 与 Java 的排序递归栈约 O(log n),Python 的 Timsort 最坏 O(n)。不计排序则 O(1)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问怎么证明这个贪心是最优的?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串的最优划分
LeetCode 2405 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题