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

这道题到底在问什么

输入

nums=[1,3,4,8,7,9,3,5,1], k=2

输出

[[1,1,3],[3,4,5],[7,8,9]]

输入

nums=[2,4,2,2,5,2], k=2

输出

[](四个 2 逼得某组要放 2 和 5,差 3 超过 k)

先想最直接的笨办法

先看组里最小的数。因为整体排过序,这一组最左边的 nums[0] 就是组内最小值,等于 1。不用挨个比,最左即最小,这是排序换来的红利。（动画第 10 步）

最优解：一步一步想明白

1. 3记住这一句:排序之后,相邻三个分一组,每组只要盯住最左和最右的差。为什么挨着分最优,是因为排完序后,当前最小的那个数,让紧挨它的两个数陪它一组,组内最大值才被压得最低,给后面留的余地最大。下面一步一步来。
2. 4第一步:排序这是原始的 nums,九个数顺序是乱的。直接在乱序上分组很难判断,所以第一步永远是排序。把它从小到大理顺,小的挤到左边、大的挪到右边,后面分组就有章法了。
3. 5已排序排完序长这样,从左到右一路不减。原来的两个 1 挤到最前,两个 3 挨在一起,最大的 9 落到最右。排好之后有个天然的好处:任意连续一段里,最小值一定在左端、最大值一定在右端,这正是下面分组要用的关键。
4. 6分组规则规则很简单:排好序后,从左往右每三个相邻的数框成一组。九个数正好切成三组,下标 0 到 2 一组、3 到 5 一组、6 到 8 一组。为什么一定挨着切,前面口诀讲过:让最小的数带上离它最近的两个,组内跨度才最小。
5. 7关键观察再点透一个关键。每一组内部本来也是排好序的,所以组里最小的就是最左那个,最大的就是最右那个。要判断这一组任意两个数的差是否都不超过 k,只要看跨度最大的那一对,也就是最右减最左。这一步把判断从三对压到了一对。
6. 8开始扫描开始正式分组。用一个指针 i 从下标 0 出发,每次处理连续三个数,处理完就往后跳 3,落到下一组的开头。i 走到 0、3、6 三个位置,分别对应三组。现在从 i 等于 0 的第一组开始。
7. 9第一组指针 i 现在在下标 0。框出连续三个数 1、1、3,这就是第一组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
8. 10定位最小先看组里最小的数。因为整体排过序,这一组最左边的 nums[0] 就是组内最小值,等于 1。不用挨个比,最左即最小,这是排序换来的红利。
9. 11定位最大再看组里最大的数。同样因为排过序,这一组最右边的 nums[2] 就是组内最大值,等于 3。现在两端都标出来了,最小 1、最大 3,跨度就藏在这两个之间。
10. 12判定算这一组的跨度:最右 3 减最左 1 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
11. 13收入答案第一组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 1 组,继续往后走。
12. 14第二组指针 i 现在在下标 3。框出连续三个数 3、4、5,这就是第二组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
13. 15定位最小先看组里最小的数。因为整体排过序,这一组最左边的 nums[3] 就是组内最小值,等于 3。不用挨个比,最左即最小,这是排序换来的红利。
14. 16定位最大再看组里最大的数。同样因为排过序,这一组最右边的 nums[5] 就是组内最大值,等于 5。现在两端都标出来了,最小 3、最大 5,跨度就藏在这两个之间。
15. 17判定算这一组的跨度:最右 5 减最左 3 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
16. 18收入答案第二组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 2 组,继续往后走。
17. 19第三组指针 i 现在在下标 6。框出连续三个数 7、8、9,这就是第三组。它们已经在大数组里排好序,所以组内也是从小到大的。先把这三个看清楚,再去量它的跨度。
18. 20定位最小先看组里最小的数。因为整体排过序,这一组最左边的 nums[6] 就是组内最小值,等于 7。不用挨个比,最左即最小,这是排序换来的红利。
19. 21定位最大再看组里最大的数。同样因为排过序,这一组最右边的 nums[8] 就是组内最大值,等于 9。现在两端都标出来了,最小 7、最大 9,跨度就藏在这两个之间。
20. 22判定算这一组的跨度:最右 9 减最左 7 等于 2。拿它和 k 等于 2 比,2 不超过 2,说明组内任意两个数的差都在允许范围内。这一组过关。
21. 23收入答案第三组 判定通过,把它整段标绿,收进答案。指针往后跳三步,准备处理下一组。到这里已经稳稳收下 3 组,三组全部到手。
22. 24收束三组全部走完。[1,1,3] 差 2、[3,4,5] 差 2、[7,8,9] 差 2,每一组的跨度都不超过 k 等于 2,划分成立。把绿色的三段按顺序拼起来,就是答案:[[1,1,3],[3,4,5],[7,8,9]],和一开始预告的对上了。只要中途有任何一组跨度超过 k,整件事立刻失败、返回空。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问