LeetCode 题解工作台
划分数组并满足最大差限制
给你一个长度为 n 的整数数组 nums ，以及一个正整数 k 。 将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件： 子数组中 任意 两个元素的差必须 小于或等于 k 。 返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一…
3
题型
9
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们先对数组进行排序，然后每次取出三个元素，如果这三个元素的最大值和最小值的差大于 ，则无法满足条件，返回空数组。否则，我们将这三个元素组成的数组加入答案数组中。 时间复杂度 $O(n \times \log n)$，空间复杂度 。其中 是数组的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：
- 子数组中 任意 两个元素的差必须 小于或等于
k。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
示例 1：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：
每个数组中任何两个元素之间的差小于或等于 2。
示例 2：
输入：nums = [2,4,2,2,5,2], k = 2
输出：[]
解释：
将 nums 划分为 2 个长度为 3 的数组的不同方式有：
- [[2,2,2],[2,4,5]] （及其排列）
- [[2,2,4],[2,2,5]] （及其排列）
因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。
示例 3：
输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
输出：[[2,2,2],[4,5,5],[5,5,7],[7,8,8],[9,9,10],[11,12,12]]
解释：
每个数组中任何两个元素之间的差小于或等于 14。
提示：
n == nums.length1 <= n <= 105n是3的倍数1 <= nums[i] <= 1051 <= k <= 105
解题思路
方法一：排序
我们先对数组进行排序，然后每次取出三个元素，如果这三个元素的最大值和最小值的差大于 ，则无法满足条件，返回空数组。否则，我们将这三个元素组成的数组加入答案数组中。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
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\cdot logN) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
The candidate understands greedy algorithms and can apply them to array manipulation.
- question_mark
The candidate recognizes the importance of sorting in solving the problem.
- question_mark
The candidate can efficiently handle edge cases, such as when no valid subarray division is possible.
常见陷阱
外企场景- error
Failing to sort the array, leading to incorrect subarray divisions.
- error
Not checking the subarray's minimum and maximum values correctly, resulting in invalid solutions.
- error
Overlooking edge cases where no valid solution exists.
进阶变体
外企场景- arrow_right_alt
Change the subarray size from 3 to another fixed value, keeping the difference condition.
- arrow_right_alt
Adjust the threshold k to a larger or smaller value and observe how the solution adapts.
- arrow_right_alt
Consider other array types, such as arrays with duplicates or large ranges of numbers.