【Leetcode】每日一题 —— No.2966

LeetCode 2966. 将数组分成差值不超过 k 的长度为 3 的子数组

原题链接：LeetCode CN - Divide Array Into Arrays With Max Difference

题目描述

给你一个整数数组 nums 和一个正整数 k。

你需要将这个数组划分为 n / 3 个长度为 3 的子数组。每个子数组必须满足：

• 子数组中任意两个元素之间的差值（绝对值）都 小于等于 k

要求返回这些子数组的列表（二维数组形式）。
如果无法划分满足条件的子数组，返回空数组 []。
若有多个解，返回任意一个即可。

示例分析

示例 1：

输入：nums = [1,3,4,8,7,9], k = 3
输出：[[1,3,4],[7,8,9]]

解释：
排序后：[1,3,4,7,8,9]
分组：
- [1,3,4] 差值最大为 3 
- [7,8,9] 差值最大为 2 

示例 2

输入：nums = [1,3,4], k = 1
输出：[]
解释：1 和 3 差为 2，超过了 1

思路解析

本质分析：

我们需要把数组分成若干组，每组正好 3 个元素，且这 3 个元素两两差值都 <= k。

解法：排序 + 贪心分组

步骤：

1. 判断 nums.size() % 3 != 0，无法整除，直接返回 []

2. 对数组进行排序

3. 每隔 3 个数组成一个子数组 [a,b,c]，只需检查：

   • c - a <= k
   • 因为排序后，a <= b <= c，最大差值在 a 和 c 之间

4. 若所有子数组都满足条件，返回所有子数组

5. 若任意一组不满足，返回 []

为什么只需判断 max - min <= k？

因为排序后：

• 差值最大的一对是 最小值 和 最大值
• 若 max - min <= k，则中间那个值也自然合法

代码实现

C++ 实现

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % 3 != 0) return {};

        sort(nums.begin(), nums.end());

        vector<vector<int>> res;
        for (int i = 0; i < n; i += 3) {
            if (nums[i + 2] - nums[i] > k) {
                return {};
            }
            res.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }
        return res;
    }
};

Go 实现

import "sort"

func divideArray(nums []int, k int) [][]int {
    n := len(nums)
    if n%3 != 0 {
        return [][]int{}
    }

    sort.Ints(nums)
    var res [][]int

    for i := 0; i < n; i += 3 {
        if nums[i+2]-nums[i] > k {
            return [][]int{}
        }
        group := []int{nums[i], nums[i+1], nums[i+2]}
        res = append(res, group)
    }

    return res
}

边界测试用例

复杂度分析

• 时间复杂度：

  • 排序：O(n log n)
  • 分组判断：O(n)
  • 总体：O(n log n)

• 空间复杂度：

  • 排序：O(1)（就地排序）
  • 结果数组：O(n)

拓展思考

1. 如果要求每个子数组 长度为任意值，但差值仍需小于等于 k？

• 就不能使用固定步长分组了
• 可考虑 双指针 + 滑动窗口

2. 如果允许的组数不确定，但要最多分组？

• 可以用贪心策略 + union set 找最大匹配组

总结

• 这是一个 排序 + 分段验证 的贪心题

• 关键在于观察：

  • 只需判断一组的最大值和最小值差是否超过 k

• 若不要求固定长度为 3，就需考虑滑动窗口等策略