LeetCode 632. 最小区间
题目描述
题意分析
给定
k个非递减有序列表，找一个闭区间，使每个列表都至少有一个数落在区间内。先比较区间长度right - left，长度相同时选左端点更小的区间。从每个列表选一个代表值后，包含它们的最短区间就是这些代表的最小值到最大值。问题因此转化为：如何有序地调整各列表的代表，找到最好的最小值与最大值组合，而不枚举所有组合。
解法：小根堆维护当前最小值
核心思路
[!blue]
初始选择每个列表的首项。小根堆保存代表的值、来源列表
row和列表内位置index，以便快速找出最小代表及其后继；另用currentMax保存所有代表的最大值。每轮循环开始时，每个列表都恰好有一个代表，所以[堆顶值, currentMax]一定覆盖全部列表。先用这个完整覆盖区间更新答案，再推进最小代表所在列表。若保留当前最小值，只推进其他列表，由于各列表有序，新代表不会比旧代表更小，右端点只能不变或增大，区间不可能更短。因此，想获得新的更优区间，必须先移走一个当前最小值。
也可以从候选左界
L理解这个过程：当所有小于L的值都被弹出后，每个列表的代表就是该列表中第一个不小于L的值。这时每组都选了满足左界要求的最小候选，它们的最大值已经是能达到的最小右界。如果某个合法区间是[L, R]，这些代表就都不超过R，算法得到的区间不会比它更差。不断推进堆顶会依次到达这些状态，因此不会漏掉最优解。替换代表时，新值不小于旧值，所有代表的最大值不会下降，所以只需执行
currentMax = max(currentMax, nextValue)，无需重新扫描堆。若最小代表所在列表已经没有后继，当前区间仍然有效，必须先比较；此后再提高左界就无法覆盖这个列表，而保留当前左界也无法缩短右端，因此可以结束搜索。堆顶值随着推进不会下降，所以后检查的区间左端点不会更小。代码只在长度严格变小时更新答案；等长时保留旧答案，就自然满足左端点优先的规则。
解题步骤
- 初始化每个列表的首项并记录最大值。
- 弹出最小项，严格更短时更新区间。
- 该列表已耗尽则结束。
- 否则补入它的下一项，并提升当前最大值。
题目保证所有列表非空，可以直接用首项初始化。只有一个列表时，第一轮就得到首项构成的零长度区间，后续同长区间不会替换它。重复值不会影响推进或覆盖关系，多个列表共享同一值时可以得到零长度答案。数值范围为 $[-10^5, 10^5]$，比较器中的差值和区间长度都不会超出
int范围。
代码实现
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
};
}
}
import "container/heap"
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+1))$，
N为元素总数、k为列表数，每个元素最多入堆一次。- 空间复杂度：$O(k)$，堆中每个列表一个代表。
关键点总结
[!green]
- 先记录当前完整覆盖，再尝试补充弹出的列表。
- 严格改善长度即可保持等长时左端优先。
易错点总结
[!yellow]
- 先推进再记录，会漏掉弹出前的合法区间。
- 某个列表耗尽后仍继续，会得到缺少该列表的伪答案。
- 等长时也覆盖旧答案，可能丢失此前更小的左端。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 76. 最小覆盖子串 | 困难 | 同样寻找覆盖所有类别的最短区间，本题类别是来源数组，原题是带重数的字符需求。 |
| 23. 合并 K 个升序链表 | 困难 | 同样每次弹出当前最小候选并补入同一来源，本题还维护当前最大值来比较覆盖区间。 |