划分数组使最大差为 K 图解题解

把数组分成几组，最少能分几组

给一个整数数组 nums 和整数 k，要把每个元素分进若干个子序列，每个元素恰好属于一个；子序列不要求连续，可以隔着原数组挑元素凑成一组。要求每一组里最大值与最小值的差不超过 k，问最少能分成几组。题面例子 nums=[3,6,1,2,5]、k 为 2 时答案是 2。

枚举所有分法试不完，先排序省在哪

子序列不要求连续、能隔着挑元素成组，n 个数硬去枚举所有分法是指数级的，试不完。可只要抓住一点，局面立刻简单：一个组合规不合规，只由组内最大值和最小值决定，和这些数原本排在数组的哪个位置毫无关系。既然位置不参与判定，就先把 nums 从小到大排好——排序不丢掉任何一种合法分法，却把数值相近的数排到了相邻。

锚点盯住组内最小值，差超了才切一刀

排序后，最左边的数是全局最小，它必须自成一组的起点——把它记作锚点 a，也就是当前这一组的最小值。右边的数一个个看过来记作 b：只要 b 减 a 不超过 k，说明 b 和组内最小值挨得够近，收进来这一组的最大差还是不超 k，并入；一旦 b 减 a ＞ k，再收就会让组内最大差破 k，只能在这里切一刀、让 b 当新一组的锚点。

为什么这样切出来的组数最少？排好序后，锚点这一组能装的就是从它开始、值不超过 a 加 k 的那一段；把这段装满，剩下的是同样的子问题，从新锚点再来。每一刀都是被差要破 k 逼着切的，少切一刀就会有组超标。

严格大于、和谁比、换不换锚点，别写错

切的条件必须是严格大于：b 减 a 正好等于 k 时，组内最大差就是 k、并没有超，得留在同组；写成大于等于会把差恰为 k 的对儿硬拆开，多分出冤枉的组。比较的对象必须是锚点 a、不是前一个元素：相邻两数差都小，首尾差未必小，像 1、2、3、4 每步差 1、首尾却差 3，只有盯住组内最小值才管得住整组。另起一组时别忘了把 a 换成当前的 b，不然后面全在拿旧最小值算差，判断连环错。排序也不能省，否则最小值飘忽不定、锚点无从谈起。

[3,6,1,2,5] 和 [2,2,4,5] 各分几组

先看 nums=[3,6,1,2,5]、k 为 2。排序后是 [1,2,3,5,6]，锚点 a=1、组数从 1 起。2 减 1 得 1、3 减 1 得 2，都不超过 2，跟 1 一组；到 5，5 减 1 得 4、已经 ＞ 2，切一刀，5 成新锚点、组数变 2；最后 6 减 5 得 1，并进第二组。分成 [1,2,3] 和 [5,6]，组数 2。

再看 nums=[2,2,4,5]、k 为 0，这回一点差都不容。排序后 [2,2,4,5]，锚点 a=2。两个 2 减 2 都得 0、不超过 0，同组；4 减 2 得 2 ＞ 0，切，a=4、组数 2；5 减 4 得 1 ＞ 0，再切，a=5、组数 3。k 为 0 逼着每种不同的值都单独成组，分出 3 组。

耗时的大头是排序：排好序是 O(n log n)，之后从左到右扫一遍是 O(n)，相加仍是 O(n log n)。只用锚点和计数两个变量，辅助空间 O(1)。

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 partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans, a = 1, nums[0]
        for b in nums:
            if b - a > k:
                a = b
                ans += 1
        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:
    int partitionArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 1, a = nums[0];
        for (int& b : nums) {
            if (b - a > k) {
                a = b;
                ++ans;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 1, a = nums[0];
        for (int b : nums) {
            if (b - a > k) {
                a = b;
                ++ans;
            }
        }
        return ans;
    }
}