LeetCode 632. 最小区间

2025-07-02 HGNULB 约 8 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 632. 最小区间

题意分析

输入是 k 个各自升序的整数数组，要找一个闭区间 $[a, b]$，使得每个数组至少有一个元素落在里面，并让 $b - a$ 最小。长度相同时取左端点更小的那个。

第一步要把「区间覆盖」这个说法翻译成更可操作的形式。一个区间 $[a, b]$ 满足条件，当且仅当能从每个数组各挑出一个元素，这 k 个元素全都落在 $[a, b]$ 里。反过来看，任取一组「每个数组各挑一个」的元素，它们的最小值和最大值围成的区间就是包含这组元素的最短区间。所以问题等价于：从每个数组各选一个数，让这 k 个数的极差最小。

约束信号有三处。第一，每个数组本身有序，这意味着「在某个数组里往后挪一位」是单调地把值变大，方向可控。第二，元素总数 $N$ 可达 $10^5$、k 可达 3500，$O(N^2)$ 之类的做法要小心。第三，元素值域包含负数，初始化极值时不能想当然地用 0。

边界上要留心：只有一个数组（答案就是任意单个元素构成的零长度区间）、所有数组的首元素都相同（答案长度为 0）、某个数组只有一个元素（它一被推进就必须停止）、以及多个区间长度相同时的左端点比较。

解法：小根堆维护当前最小值

核心思路

暴力做法是枚举所有「每数组各选一个」的组合，共 $\prod nums_i $ 种，指数级，完全不可行。

换个角度：把所有元素连同它所属的数组编号打包排序，问题就变成了在这条总长 $N$ 的序列上找一个最短窗口，使窗口内出现过全部 k 种编号——这是标准的最小覆盖子串型滑动窗口，$O(N \log N)$ 可行。这条路是对的，但要额外排序、额外维护计数表。

顺着「每数组各选一个」再想一步，能得到更贴合输入结构的做法。维护一组指针，第 i 个指针指向第 i 个数组当前选中的位置，初始全指向各自开头。这组选择的最小值和最大值围成一个合法区间。想让区间变短，只有两条路：抬高最小值，或者压低最大值。而压低最大值是做不到的——所有指针只能往后走，值只会变大。所以唯一有意义的动作是推进最小值所在的那个数组的指针。

这个动作还必须是「必做」的：只要不推进当前最小值，这个最小值就一直卡在那里，区间左端点没法抬高，长度不可能变短。于是每一步的动作是唯一确定的，整个过程没有分支，退化成一条线性的推进链。

要 $O(\log k)$ 地取出「当前最小值属于哪个数组」，自然想到小根堆：堆里恰好放 k 个元素，每个数组各一个。最大值则不需要堆——因为每次只推入一个新元素，而新元素一定不小于它替换掉的那个（同数组的后一位更大），所以最大值只可能被新推入的元素刷新，用一个变量跟着取最大即可。

显式的不变量是：任意时刻堆中恰好含 k 个元素，来自 k 个不同数组，currentMax 等于这 k 个元素的最大值；堆顶就是这 k 个元素的最小值，二者围成的区间是当前指针配置下的最短合法区间。一旦某个数组被推完，就再也凑不齐 k 个，循环必须终止。

关于并列长度取左端点最小：因为每一步都在抬高最小值，候选区间的左端点是单调不降的，先遇到的左端点更小，所以更新答案时用严格小于（而不是小于等于）就自动满足了这条要求。

解题步骤

把每个数组的首元素连同「所属数组下标」和「在数组内的位置」一起推入小根堆，同时用一个变量 currentMax 记录这 k 个首元素的最大值。元素必须带上数组下标，否则弹出后不知道该推进谁。

把答案初始化成一个宽到不可能被超越的区间，例如左端 0、右端 Integer.MAX_VALUE。初值必须保证第一次比较一定成立，用 [0, 0] 这种零长度初值会让答案永远更新不进去。

循环条件是「堆大小等于 k」。这条件同时表达了「每个数组都还有代表在场」这个合法性前提。

每轮弹出堆顶作为 currentMin，它和 currentMax 围成当前区间。

若 $currentMax - currentMin$ 严格小于已记录的最优长度，就更新答案。用严格小于是为了在长度并列时保留先遇到的、左端点更小的那个。

取出弹出元素所在数组的下一个位置。若已经越过该数组末尾，说明这个数组再也无法提供代表，直接跳出循环。

否则把下一个元素推入堆，并用它更新 currentMax。这一步的更新不能漏：新元素是唯一可能刷新最大值的来源。

循环结束后返回记录的最优区间。

以 nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 走一遍：初始把三个首元素 4（行 0）、0（行 1）、5（行 2）推入堆，currentMax = 5，答案初值是 $[0, 2147483647]$。

第 1 轮弹出 0（行 1），区间是 $[0, 5]$，长度 5，小于初值长度，答案更新为 $[0, 5]$。推进行 1 到 9，currentMax 变成 9。堆里是 4、5、9。

第 2 轮弹出 4（行 0），区间 $[4, 9]$ 长度 5，不严格小于 5，不更新。推进行 0 到 10，currentMax = 10。堆里是 5、9、10。

第 3 轮弹出 5（行 2），区间 $[5, 10]$ 长度 5，不更新。推进行 2 到 18，currentMax = 18。堆里是 9、10、18。

第 4 轮弹出 9（行 1），区间 $[9, 18]$ 长度 9，不更新。推进行 1 到 12，currentMax 仍是 18。堆里是 10、12、18。

第 5 轮弹出 10（行 0），区间 $[10, 18]$ 长度 8，不更新。推进行 0 到 15，currentMax 仍是 18。堆里是 12、15、18。

第 6 轮弹出 12（行 1），区间 $[12, 18]$ 长度 6，不更新。推进行 1 到 20，currentMax = 20。堆里是 15、18、20。

第 7 轮弹出 15（行 0），区间 $[15, 20]$ 长度 5，不严格小于 5，不更新。推进行 0 到 24，currentMax = 24。堆里是 18、20、24。

第 8 轮弹出 18（行 2），区间 $[18, 24]$ 长度 6，不更新。推进行 2 到 22，currentMax 仍是 24。堆里是 20、22、24。

第 9 轮弹出 20（行 1），区间 $[20, 24]$ 长度 4，严格小于 5，答案更新为 $[20, 24]$。行 1 的下一个位置是 4，而它只有 4 个元素，越界了，跳出循环。

返回 $[20, 24]$。检验一下：24 来自第一个数组，20 来自第二个数组，22 来自第三个数组，三者都落在区间内，覆盖成立。

代码实现

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int currentMax = Integer.MIN_VALUE;
        for (int row = 0; row < nums.size(); row++) {
            int value = nums.get(row).get(0);
            heap.offer(new int[]{value, row, 0});
            currentMax = Math.max(currentMax, value);
        }

        int bestLeft = 0;
        int bestRight = Integer.MAX_VALUE;
        while (heap.size() == nums.size()) {
            int[] cur = heap.poll();
            int currentMin = cur[0];
            if (currentMax - currentMin < bestRight - bestLeft) {
                bestLeft = currentMin;
                bestRight = currentMax;
            }

            int row = cur[1];
            int index = cur[2] + 1;
            if (index == nums.get(row).size()) {
                break;
            }
            int nextValue = nums.get(row).get(index);
            heap.offer(new int[]{nextValue, row, index});
            currentMax = Math.max(currentMax, nextValue);
        }
        return new int[]{bestLeft, bestRight};
    }
}

type RangeNode struct {
    value int
    row   int
    index int
}

type RangeHeap []RangeNode

func (h RangeHeap) Len() int {
    return len(h)
}

func (h RangeHeap) Less(i int, j int) bool {
    return h[i].value < h[j].value
}

func (h RangeHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *RangeHeap) Push(x any) {
    *h = append(*h, x.(RangeNode))
}

func (h *RangeHeap) Pop() any {
    old := *h
    node := old[len(old)-1]
    *h = old[:len(old)-1]
    return node
}

func smallestRange(nums [][]int) []int {
    h := &RangeHeap{}
    currentMax := -1 << 31
    for row := 0; row < len(nums); row++ {
        value := nums[row][0]
        heap.Push(h, RangeNode{value: value, row: row, index: 0})
        if value > currentMax {
            currentMax = value
        }
    }

    bestLeft := 0
    bestRight := 1<<31 - 1
    for h.Len() == len(nums) {
        cur := heap.Pop(h).(RangeNode)
        currentMin := cur.value
        if currentMax-currentMin < bestRight-bestLeft {
            bestLeft = currentMin
            bestRight = currentMax
        }

        nextIndex := cur.index + 1
        if nextIndex == len(nums[cur.row]) {
            break
        }
        nextValue := nums[cur.row][nextIndex]
        heap.Push(h, RangeNode{value: nextValue, row: cur.row, index: nextIndex})
        if nextValue > currentMax {
            currentMax = nextValue
        }
    }
    return []int{bestLeft, bestRight}
}

复杂度分析

时间复杂度：$O(N \log k)$，N 是所有元素总数，k 是数组个数。

空间复杂度：$O(k)$。

关键点总结

堆中始终保持每个数组一个候选元素。
当前最大值需要单独维护。
每次推进当前最小值所在的数组，才有机会缩小区间。

易错点总结

只维护最小值，忘记更新当前最大值。
某个数组耗尽后继续循环，导致区间不再覆盖所有数组。
相同区间长度时没有保留更小左端点，不过本算法按推进顺序天然优先遇到较小左端点。

相似题目

题目	难度	考察点
23. 合并 K 个升序链表	困难	同样用小根堆维护多个有序序列头