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

这道题到底在问什么

输入

nums = [3,6,1,2,5], k = 2

输出

2

输入

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

输出

3

先想最直接的笨办法

排好序后变成 1、2、3、6、7、8、11、12。现在最左边的 1 是全局最小,也是第一组的最小值。接下来右指针从左往右一个一个走,拿每个数和当前组的锚点比,决定它是留在本组还是另起一组。（动画第 5 步）

最优解：一步一步想明白

1. 3记牢这一句:排序后,锚点 a 盯住当前组的最小值。b - a ≤ k 就归本组,b - a > k 就另起一组。贪心之所以对,是因为排好序后,每一组尽量往右多装、直到差要超过 k 才切,组数一定最少。下面从头扫一遍。
2. 4先看原始输入,8 个数乱序排列。整个贪心都建立在有序之上,因为只有排好序,当前组的最小值才恒等于组里第一个进来的数。所以第一步永远是把 nums 从小到大排好。
3. 5排好序后变成 1、2、3、6、7、8、11、12。现在最左边的 1 是全局最小,也是第一组的最小值。接下来右指针从左往右一个一个走,拿每个数和当前组的锚点比,决定它是留在本组还是另起一组。
4. 6开扫之前把规则钉死。紫色是正在看的数 b,下方那个标记 a 是当前组的锚点,也就是本组最小值。每一步只做一件事:算 b - a,如果不超过 2 就并进这一组,如果超过 2 就在 b 这里切一刀、另起一组。锚点从最左的 1 起步,第一组先开着。
5. 7扫描从最左边开始。第一个数 1 无处可比,它自己就得开一组,并且当仁不让地成为这一组的锚点 a,也就是这一组的最小值。后面所有数,都要拿来和它算差。
6. 8把 1 收进第 1 组,这一组现在只有它一个,锚点也是它。继续往右看下一个数。
7. 9右指针走到 2。当前这一组的锚点是 1,算一下 2 减 1 等于 1。这个差 1 不超过 2,说明 2 和本组最小值挨得够近,可以安心并进来。
8. 10把 2 并进当前组,本组现在是 [1, 2]。注意锚点 a 依然是组里最小的 1,没有变,后面的数还是拿来和它比。分组数保持 1。
9. 11右指针走到 3。当前这一组的锚点是 1,算一下 3 减 1 等于 2。这个差 2 不超过 2,说明 3 和本组最小值挨得够近,可以安心并进来。
10. 12把 3 并进当前组,本组现在是 [1, 2, 3]。注意锚点 a 依然是组里最小的 1,没有变,后面的数还是拿来和它比。分组数保持 1。
11. 13右指针走到 6。当前这一组的锚点是 1,算一下 6 减 1 等于 5。这个差 5 已经大于 2,说明 6 和本组最小值拉得太开,再塞进来这一组的最大差就要爆 2。它进不了这一组。
12. 14于是在这里切一刀。前面那组 [1, 2, 3] 就此封口,它内部最大差是 2,稳稳不超过 2。6 成为新一组的第一个数、也是新锚点,分组数从 1 涨到 2。
13. 15右指针走到 7。当前这一组的锚点是 6,算一下 7 减 6 等于 1。这个差 1 不超过 2,说明 7 和本组最小值挨得够近,可以安心并进来。
14. 16把 7 并进当前组,本组现在是 [6, 7]。注意锚点 a 依然是组里最小的 6,没有变,后面的数还是拿来和它比。分组数保持 2。
15. 17右指针走到 8。当前这一组的锚点是 6,算一下 8 减 6 等于 2。这个差 2 不超过 2,说明 8 和本组最小值挨得够近,可以安心并进来。
16. 18把 8 并进当前组,本组现在是 [6, 7, 8]。注意锚点 a 依然是组里最小的 6,没有变,后面的数还是拿来和它比。分组数保持 2。
17. 19右指针走到 11。当前这一组的锚点是 6,算一下 11 减 6 等于 5。这个差 5 已经大于 2,说明 11 和本组最小值拉得太开,再塞进来这一组的最大差就要爆 2。它进不了这一组。
18. 20于是在这里切一刀。前面那组 [6, 7, 8] 就此封口,它内部最大差是 2,稳稳不超过 2。11 成为新一组的第一个数、也是新锚点,分组数从 2 涨到 3。
19. 21右指针走到 12。当前这一组的锚点是 11,算一下 12 减 11 等于 1。这个差 1 不超过 2,说明 12 和本组最小值挨得够近,可以安心并进来。
20. 22把 12 并进当前组,本组现在是 [11, 12]。注意锚点 a 依然是组里最小的 11,没有变,后面的数还是拿来和它比。分组数保持 3。
21. 23扫完了,回放一遍。整条序列被切成三段:[1, 2, 3]、[6, 7, 8]、[11, 12]。相邻两段之间,正是那两处 b - a 大于 2 的地方切开的。绿一段、蓝一段、绿一段,颜色只为让你看清分界,一共 3 组。
22. 24再逐组核对一遍最大差。第一组 3 减 1 等于 2,第二组 8 减 6 等于 2,第三组 12 减 11 等于 1,三组全都不超过 2,完全合规。而且你没法再省:每一刀都是被逼着切的,少切一刀就一定有组会爆 2。所以最少划分数就是 3。

⚠️ 容易写错的地方

完整代码（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 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

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

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

复杂度

面试官可能追问