题目描述
思路解析动画文字版
记住这一句:排序之后,相邻三个分一组,每组只要盯住最左和最右的差。为什么挨着分最优,是因为排完序后,当前最小的那个数,让紧挨它的两个数陪它一组,组内最大值才被压得最低,给后面留的余地最大。下面一步一步来。
原始数组 · 顺序杂乱,先排序：这是原始的 nums,九个数顺序是乱的。直接在乱序上分组很难判断,所以第一步永远是排序。把它从小到大理顺,小的挤到左边、大的挪到右边,后面分组就有章法了。
排序后 · 从小到大排好：排完序长这样,从左到右一路不减。原来的两个 1 挤到最前,两个 3 挨在一起,最大的 9 落到最右。排好之后有个天然的好处:任意连续一段里,最小值一定在左端、最大值一定在右端,这正是下面分组要用的关键。
每相邻三个分一组：规则很简单:排好序后,从左往右每三个相邻的数框成一组。九个数正好切成三组,下标 0 到 2 一组、3 到 5 一组、6 到 8 一组。为什么一定挨着切,前面口诀讲过:让最小的数带上离它最近的两个,组内跨度才最小。
组内只需比较最左与最右：再点透一个关键。每一组内部本来也是排好序的,所以组里最小的就是最左那个,最大的就是最右那个。要判断这一组任意两个数的差是否都不超过 k,只要看跨度最大的那一对,也就是最右减最左。这一步把判断从三对压到了一对。
指针 i 从 0 开始,每次跳 3：开始正式分组。用一个指针 i 从下标 0 出发,每次处理连续三个数,处理完就往后跳 3,落到下一组的开头。i 走到 0、3、6 三个位置,分别对应三组。现在从 i 等于 0 的第一组开始。
第一组 · 取出下标 0 到 2：指针 i 现在在下标 0。框出连续三个数 1、1、3,这就是第一组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
第一组 · 组内最小 = 1(最左)：先看组里最小的数。因为整体排过序,这一组最左边的 nums[0] 就是组内最小值,等于 1。不用挨个比,最左即最小,这是排序换来的红利。
第一组 · 组内最大 = 3(最右)：再看组里最大的数。同样因为排过序,这一组最右边的 nums[2] 就是组内最大值,等于 3。现在两端都标出来了,最小 1、最大 3,跨度就藏在这两个之间。
第一组 · 最右减最左 = 2,和 k=2 比：算这一组的跨度:最右 3 减最左 1 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
第一组 · 合格,收入答案(已收 1 组)：第一组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 1 组,继续往后走。
第二组 · 取出下标 3 到 5：指针 i 现在在下标 3。框出连续三个数 3、4、5,这就是第二组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
第二组 · 组内最小 = 3(最左)：先看组里最小的数。因为整体排过序,这一组最左边的 nums[3] 就是组内最小值,等于 3。不用挨个比,最左即最小,这是排序换来的红利。
第二组 · 组内最大 = 5(最右)：再看组里最大的数。同样因为排过序,这一组最右边的 nums[5] 就是组内最大值,等于 5。现在两端都标出来了,最小 3、最大 5,跨度就藏在这两个之间。
第二组 · 最右减最左 = 2,和 k=2 比：算这一组的跨度:最右 5 减最左 3 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
第二组 · 合格,收入答案(已收 2 组)：第二组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 2 组,继续往后走。
第三组 · 取出下标 6 到 8：指针 i 现在在下标 6。框出连续三个数 7、8、9,这就是第三组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
第三组 · 组内最小 = 7(最左)：先看组里最小的数。因为整体排过序,这一组最左边的 nums[6] 就是组内最小值,等于 7。不用挨个比,最左即最小,这是排序换来的红利。
第三组 · 组内最大 = 9(最右)：再看组里最大的数。同样因为排过序,这一组最右边的 nums[8] 就是组内最大值,等于 9。现在两端都标出来了,最小 7、最大 9,跨度就藏在这两个之间。
第三组 · 最右减最左 = 2,和 k=2 比：算这一组的跨度:最右 9 减最左 7 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
第三组 · 合格,收入答案(已收 3 组)：第三组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 3 组,三组全部到手。
回放 · 三组全部合格,划分成立：三组全部走完。[1,1,3] 差 2、[3,4,5] 差 2、[7,8,9] 差 2,每一组的跨度都不超过 k 等于 2,划分成立。把绿色的三段按顺序拼起来,就是答案:[[1,1,3],[3,4,5],[7,8,9]],和一开始预告的对上了。只要中途有任何一组跨度超过 k,整件事立刻失败、返回空。
边界想清:差恰好等于 k 算合法、超过 k 即返回空、四个 2 那组逼出的 2 和 5 差 3 超标故无解。
面试重点:排序加贪心相邻三个一组、交换论证证明最优、瓶颈在排序 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 divideArray(self, nums: List[int], k: int) -> List[List[int]]: nums.sort() ans = [] n = len(nums) for i in range(0, n, 3): t = nums[i : i + 3] if t[2] - t[0] > k: return [] ans.append(t) return ans复杂度
- 时间：O(n log n)，排序是主要开销,占 O(n log n)。排完后从头到尾每三个一组扫一遍,只做常数次比较和取值,是 O(n)。两者相加由排序主导,整体 O(n log n)
- 空间：O(n) / O(log n)，按峰值算。返回的答案本身要占 O(n)。若不计输出只看排序的额外开销:C plus plus 与 Java 的排序递归栈约 O(log n),Python 的 Timsort 最坏 O(n);辅助变量本身是 O(1)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么贪心地取相邻三个是对的?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分发糖果
LeetCode 135 · 困难 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题