划分数组并满足最大差限制 图解题解

把数组切成一组组三个，组内差不能太大

给一个长度是 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 的倍数题目已保证，跳三格正好切完。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n; i += 3) {
            vector<int> t = {nums[i], nums[i + 1], nums[i + 2]};
            if (t[2] - t[0] > k) {
                return {};
            }
            ans.emplace_back(t);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[][] ans = new int[n / 3][];
        for (int i = 0; i < n; i += 3) {
            int[] t = Arrays.copyOfRange(nums, i, i + 3);
            if (t[2] - t[0] > k) {
                return new int[][] {};
            }
            ans[i / 3] = t;
        }
        return ans;
    }
}