难度: Medium
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：
nums 中的 每个 元素都必须 恰好 存在于某个子数组中。k 。返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
示例 1：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2 输出：[[1,1,3],[3,4,5],[7,8,9]] 解释：可以将数组划分为以下子数组：[1,1,3]，[3,4,5] 和 [7,8,9] 。 每个子数组中任意两个元素的差都小于或等于 2 。 注意，元素的顺序并不重要。
示例 2：
输入：nums = [1,3,3,2,7,3], k = 3 输出：[] 解释：无法划分数组满足所有条件。
提示：
n == nums.length1 <= n <= 105n 是 3 的倍数1 <= nums[i] <= 1051 <= k <= 105运行时间: 112 ms
内存: 31.7 MB
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):
if nums[i + 2] - nums[i] > k:
return []
ans.append(nums[i:i + 3])
return ans
该题解首先对数组进行排序，排序后的数组中相邻元素的差会是最小的。由于子数组的长度固定为3，题解采用了一个循环，步长为3，从排序后的数组中依次取出每3个元素组成子数组。在每次取出子数组时，检查子数组中的最大值和最小值的差是否大于k。如果大于k，则说明无法满足题目要求，直接返回空数组。如果所有子数组都满足条件，则将这些子数组返回。这种方法使用了贪心的策略，即尽可能地将排序后相邻的元素分配到同一个子数组中，利用排序后元素间差值最小的特性来满足差值条件。
时间复杂度: O(n log n)
空间复杂度: O(log n)
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): # 以步长3遍历数组
if nums[i + 2] - nums[i] > k: # 检查每个子数组的最大元素与最小元素的差是否超过k
return [] # 如果超过k，直接返回空数组
ans.append(nums[i:i + 3]) # 将符合条件的子数组添加到答案中
return ans # 返回最终的答案数组
排序是处理这个问题的首要步骤，因为排序后相邻元素的差值会最小，这有助于最大限度地减小子数组内的最大值与最小值的差值。这种方法使得在进行子数组分割时，可以较容易地满足最大差值不超过k的条件。如果数组未排序，相邻元素的差值可能很大，难以控制子数组内的最大差值，从而影响整体的分割策略。
在本题解策略中，由于数组已经排序并且以固定步长3来划分子数组，每个子数组内部的元素是连续的三个元素。因此，如果一个子数组满足最大值与最小值的差不超过k，后续的子数组也会独立地进行检查。这里不存在因前一个子数组的分配而影响到后续子数组的情况，因为子数组的分配是基于排序后的固定位置，不依赖于其他子数组的配置。
题解中没有显式处理数组长度不是3的倍数的情况，这是一个缺陷。在实际应用中，应该在循环遍历数组之前检查数组长度是否为3的倍数。如果不是，应该返回一个错误或者空数组，因为题目要求子数组长度固定为3，如果无法完全分割成多个长度为3的子数组，则无法满足题目的要求。
本题的贪心策略在于尽可能利用排序后相邻元素之间差值最小的特性，通过固定步长（本例为3）选择连续的元素来形成子数组。这种方法有效，因为在已排序的数组中，连续的几个元素之间的最大差值通常比非连续元素的差值小，从而更有可能满足差值不大于k的条件。这种策略简化了问题，避免了复杂的子数组重组和重新计算差值的需要，提高了算法的效率和实现的简洁性。