题目描述
思路解析
一句话答案：LeetCode 2966 划分数组并满足最大差限制：把数组每三个一组、组内最大最小之差不超过 k。先从小到大排序，再相邻三个一组，只看每组最右减最左是否超 k，超了就返回空，时间 O(n log n)。
把数组切成一组组三个，组内差不能太大
给一个长度是 3 的倍数的数组 nums 和一个正整数 k。要把 nums 分成若干组、每组正好三个数，同一组里任意两个数的差都不超过 k。能切就返回任意一种切法，切不出来返回空数组。题面例子 nums=[1,3,4,8,7,9,3,5,1]、k 等于 2，一种合法答案是 [[1,1,3],[3,4,5],[7,8,9]]。
组内三对差都要满足，分法又那么多
同一组三个数，两两就有三对差都得压在 k 以内；九个数凑成三组的分法极多，逐个枚举再逐组验差，数一大就爆炸。难处在于既不知道哪三个数该放一起，定了一组又得比三对差才敢下结论，试遍所有分法，n 稍大就跑不动。
为什么排完序，紧挨着的三个一组最省心
先把 nums 从小到大排序。排完之后有个好处：任意连续一段里，最小值一定落在最左、最大值一定落在最右。于是判断一组三个数的跨度，不必比三对，只看最右减最左这一对——它是组里跨度最大的一对，它不超 k，另外两对更小、自然也不超。
再说为什么取紧挨着的三个。用贪心，也就是每步拿当下最划算的、不回头：排完序后，还没分掉的最小那个数总得找两个伙伴，让紧挨它的两个陪它一组，这组最大值压到最低，给后面留的余地最大。这叫交换论证，即假设有更优分法，把它调成相邻分组也不会更差，所以每三个相邻框成一组就是最优。
从左到右每三个切一刀，一超标就收手
排好序后，从下标 0 起，每次取连续三个数当一组，取完往后跳三格到下一组开头，直到走完。每取一组就看最右减最左：只要差＞k，这组装不下，整个数组也切不出合法划分，立刻返回空数组；不超 k 就把这组收进答案，继续往后切。全部切完，收集的三元组拼起来就是答案。
拿题面这九个数排完序一刀刀切
先排序：[1,3,4,8,7,9,3,5,1] 从小到大理顺成 [1,1,3,3,4,5,7,8,9]，两个 1 挤到最前，9 落到最右。
从下标 0 起切。第一组取 [1,1,3]，最右 3 减最左 1 等于 2，不超过 k，收下。跳到下标 3，第二组取 [3,4,5]，5 减 3 等于 2，同样不超，收下。再跳到下标 6，第三组取 [7,8,9]，9 减 7 等于 2，收下。三组全合格，答案就是 [[1,1,3],[3,4,5],[7,8,9]]。
复杂度，以及差恰好等于 k 算不算数
排序 O(n log n) 外只线性扫一遍：排完后每三个一组走一趟是 O(n)，整体仍是 O(n log n)。空间上答案占 O(n)，只看排序的额外开销，C++ 和 Java 的递归栈约 O(log n)、Python 的 Timsort（Python 内置排序）最坏 O(n)。
两个边界得拎清。其一，差恰好等于 k 合法，判超标得用严格大于：差＞k 才算坏。其二，nums=[2,4,2,2,5,2]、k 为 2 为什么无解——排成 [2,2,2,2,4,5]，第一组 [2,2,2] 差 0 过关，第二组只剩 [2,4,5]，5 减 2 等于 3，＞2，返回空数组，四个 2 把一个挤进了 5 那组。至于 n 是 3 的倍数题目已保证，跳三格正好切完。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句:排序之后,相邻三个分一组,每组只要盯住最左和最右的差。为什么挨着分最优,是因为排完序后,当前最小的那个数,让紧挨它的两个数陪它一组,组内最大值才被压得最低,给后面留的余地最大。下面一步一步来。
原始数组 · 顺序杂乱,先排序：这是原始的 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题