最小区间 图解题解

这道题到底在问什么

输入

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

输出

[20, 24]

先想最直接的笨办法

回头看整条路径:我们从没枚举任何区间,只是反复「读 k 路的最小值与最大值得到一个候选窗口、刷新最优、再把最小值所在的那一路推进一格」。最小值一路右移,窗口左端越收越紧,直到某路到头无法再补。最终最短区间 = [20, 24],宽度 4。（动画第 26 步）

最优解：一步一步想明白

1. 3记住这句:堆里永远是「每个列表当前指针的一个值」共 k 个,堆顶最小值当区间左端、curMax 当区间右端。每一轮拿当前窗口去刷新最优答案,然后把最小的那一路指针往后挪、压入下一个值。某个列表没有下一个值时就停下。
2. 4先建堆。把每个列表的第一个数都放进小顶堆。L0 的首个值 4 入堆,当前窗口最大值 curMax = 4。
3. 5L1 的第一个数 0 入堆。同时更新窗口最大值:curMax = 4。堆里现在有 2 个值,正是 2 路指针各指一个。
4. 6L2 的第一个数 5 入堆。同时更新窗口最大值:curMax = 5。堆里现在有 3 个值,正是 3 路指针各指一个。
5. 7三路起点都进堆了:堆顶最小 0、窗口最大 5,起始候选区间是 [0, 5],宽 5。它已经覆盖三个列表,只是还很宽,接下来一步步把左端往右收。
6. 8第一轮:堆顶最小是 0(来自 L1),窗口右端是 curMax = 5,宽度 5。这比之前最优更短,刷新最优为 [0, 5]。
7. 9弹出最小的 0,把 L1 的指针往后挪一格,压入它的下一个值 9。它比原 curMax 5 还大,窗口右端被它顶到 curMax = 9。新堆顶最小是 4,窗口收成了 [4, 9]。
8. 10第二轮:堆顶最小是 4(来自 L0),窗口 [4, 9] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。
9. 11弹出最小的 4,把 L0 的指针往后挪一格,压入它的下一个值 10。它比原 curMax 9 还大,窗口右端被它顶到 curMax = 10。新堆顶最小是 5,窗口收成了 [5, 10]。
10. 12第三轮:堆顶最小是 5(来自 L2),窗口 [5, 10] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。
11. 13弹出最小的 5,把 L2 的指针往后挪一格,压入它的下一个值 18。它比原 curMax 10 还大,窗口右端被它顶到 curMax = 18。新堆顶最小是 9,窗口收成了 [9, 18]。
12. 14第四轮:堆顶最小是 9(来自 L1),窗口 [9, 18] 宽度 9,不比已知最优 [0, 5] 短,最优保持不动。
13. 15弹出最小的 9,把 L1 的指针往后挪一格,压入它的下一个值 12。它不超过 curMax 18,窗口右端 curMax 维持 18。新堆顶最小是 10,窗口收成了 [10, 18]。
14. 16第五轮:堆顶最小是 10(来自 L0),窗口 [10, 18] 宽度 8,不比已知最优 [0, 5] 短,最优保持不动。
15. 17弹出最小的 10,把 L0 的指针往后挪一格,压入它的下一个值 15。它不超过 curMax 18,窗口右端 curMax 维持 18。新堆顶最小是 12,窗口收成了 [12, 18]。
16. 18第六轮:堆顶最小是 12(来自 L1),窗口 [12, 18] 宽度 6,不比已知最优 [0, 5] 短,最优保持不动。
17. 19弹出最小的 12,把 L1 的指针往后挪一格,压入它的下一个值 20。它比原 curMax 18 还大,窗口右端被它顶到 curMax = 20。新堆顶最小是 15,窗口收成了 [15, 20]。
18. 20第七轮:堆顶最小是 15(来自 L0),窗口 [15, 20] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。
19. 21弹出最小的 15,把 L0 的指针往后挪一格,压入它的下一个值 24。它比原 curMax 20 还大,窗口右端被它顶到 curMax = 24。新堆顶最小是 18,窗口收成了 [18, 24]。
20. 22第八轮:堆顶最小是 18(来自 L2),窗口 [18, 24] 宽度 6,不比已知最优 [0, 5] 短,最优保持不动。
21. 23弹出最小的 18,把 L2 的指针往后挪一格,压入它的下一个值 22。它不超过 curMax 24,窗口右端 curMax 维持 24。新堆顶最小是 20,窗口收成了 [20, 24]。
22. 24第九轮:堆顶最小是 20(来自 L1),窗口右端是 curMax = 24,宽度 4。这比之前最优更短,刷新最优为 [20, 24]。
23. 25要缩短区间必须把最小的 20 往后挪,可它来自 L1,而 L1 已经到末尾、没有下一个值可补。一旦弹掉它,堆里就缺了 L1 这一路,剩下的 [22, 24] 不再覆盖全部列表、不是有效窗口。所以停在最后一个有效窗口,最终答案 = [20, 24]。
24. 26回头看整条路径:我们从没枚举任何区间,只是反复「读 k 路的最小值与最大值得到一个候选窗口、刷新最优、再把最小值所在的那一路推进一格」。最小值一路右移,窗口左端越收越紧,直到某路到头无法再补。最终最短区间 = [20, 24],宽度 4。

⚠️ 容易写错的地方

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

from typing import List
import heapq
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = []
        cur_max = -10**18
        for i, arr in enumerate(nums):
            heapq.heappush(heap, (arr[0], i, 0))
            cur_max = max(cur_max, arr[0])
        best = [-10**9, 10**9]
        while True:
            val, i, j = heapq.heappop(heap)
            if cur_max - val < best[1] - best[0]:
                best = [val, cur_max]
            if j + 1 == len(nums[i]):
                return best
            nxt = nums[i][j + 1]
            cur_max = max(cur_max, nxt)
            heapq.heappush(heap, (nxt, i, j + 1))

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using T = tuple<int,int,int>;
        priority_queue<T, vector<T>, greater<T>> pq;
        int curMax = INT_MIN;
        for (int i = 0; i < (int)nums.size(); ++i) { pq.push({nums[i][0], i, 0}); curMax = max(curMax, nums[i][0]); }
        vector<int> best{-1000000000, 1000000000};
        while (true) {
            auto [val, i, j] = pq.top(); pq.pop();
            if (curMax - val < best[1] - best[0]) best = {val, curMax};
            if (j + 1 == (int)nums[i].size()) return best;
            int nxt = nums[i][j + 1];
            curMax = max(curMax, nxt);
            pq.push({nxt, i, j + 1});
        }
    }
};

import java.util.*;
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) { pq.offer(new int[]{nums.get(i).get(0), i, 0}); curMax = Math.max(curMax, nums.get(i).get(0)); }
        int[] best = {-1_000_000_000, 1_000_000_000};
        while (true) {
            int[] cur = pq.poll();
            if (curMax - cur[0] < best[1] - best[0]) best = new int[]{cur[0], curMax};
            if (cur[2] + 1 == nums.get(cur[1]).size()) return best;
            int nxt = nums.get(cur[1]).get(cur[2] + 1);
            curMax = Math.max(curMax, nxt);
            pq.offer(new int[]{nxt, cur[1], cur[2] + 1});
        }
    }
}

复杂度

面试官可能追问