题目描述
思路解析
一句话答案：LeetCode 2294 划分数组使最大差为 K：排序后从最小值起贪心分组，和当前组锚点差 ＞ k 就另起一组，靠有序保证每组尽量多装、组数最少，时间 O(n log n)。
把数组分成几组，最少能分几组
给一个整数数组 nums 和整数 k，要把每个元素分进若干个子序列，每个元素恰好属于一个；子序列不要求连续，可以隔着原数组挑元素凑成一组。要求每一组里最大值与最小值的差不超过 k，问最少能分成几组。题面例子 nums=[3,6,1,2,5]、k 为 2 时答案是 2。
枚举所有分法试不完，先排序省在哪
子序列不要求连续、能隔着挑元素成组，n 个数硬去枚举所有分法是指数级的，试不完。可只要抓住一点，局面立刻简单：一个组合规不合规，只由组内最大值和最小值决定，和这些数原本排在数组的哪个位置毫无关系。既然位置不参与判定，就先把 nums 从小到大排好——排序不丢掉任何一种合法分法，却把数值相近的数排到了相邻。
锚点盯住组内最小值，差超了才切一刀
排序后，最左边的数是全局最小，它必须自成一组的起点——把它记作锚点 a，也就是当前这一组的最小值。右边的数一个个看过来记作 b：只要 b 减 a 不超过 k，说明 b 和组内最小值挨得够近，收进来这一组的最大差还是不超 k，并入；一旦 b 减 a ＞ k，再收就会让组内最大差破 k，只能在这里切一刀、让 b 当新一组的锚点。
为什么这样切出来的组数最少？排好序后，锚点这一组能装的就是从它开始、值不超过 a 加 k 的那一段；把这段装满，剩下的是同样的子问题，从新锚点再来。每一刀都是被差要破 k 逼着切的，少切一刀就会有组超标。
严格大于、和谁比、换不换锚点，别写错
切的条件必须是严格大于：b 减 a 正好等于 k 时，组内最大差就是 k、并没有超，得留在同组；写成大于等于会把差恰为 k 的对儿硬拆开，多分出冤枉的组。比较的对象必须是锚点 a、不是前一个元素：相邻两数差都小，首尾差未必小，像 1、2、3、4 每步差 1、首尾却差 3，只有盯住组内最小值才管得住整组。另起一组时别忘了把 a 换成当前的 b，不然后面全在拿旧最小值算差，判断连环错。排序也不能省，否则最小值飘忽不定、锚点无从谈起。
[3,6,1,2,5] 和 [2,2,4,5] 各分几组
先看 nums=[3,6,1,2,5]、k 为 2。排序后是 [1,2,3,5,6]，锚点 a=1、组数从 1 起。2 减 1 得 1、3 减 1 得 2，都不超过 2，跟 1 一组；到 5，5 减 1 得 4、已经 ＞ 2，切一刀，5 成新锚点、组数变 2；最后 6 减 5 得 1，并进第二组。分成 [1,2,3] 和 [5,6]，组数 2。
再看 nums=[2,2,4,5]、k 为 0，这回一点差都不容。排序后 [2,2,4,5]，锚点 a=2。两个 2 减 2 都得 0、不超过 0，同组；4 减 2 得 2 ＞ 0，切，a=4、组数 2；5 减 4 得 1 ＞ 0，再切，a=5、组数 3。k 为 0 逼着每种不同的值都单独成组，分出 3 组。
耗时的大头是排序：排好序是 O(n log n)，之后从左到右扫一遍是 O(n)，相加仍是 O(n log n)。只用锚点和计数两个变量，辅助空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:排序后,锚点 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题