LeetCode 632. 最小区间

Categories:

题目描述
思路分析
1. 解法一：多路归并 + 小根堆（推荐）
相似题目

题目描述

✅ 632. 最小区间

思路分析

解法一：多路归并 + 小根堆（推荐）

核心思路：

每个列表取一个指针，堆中保存当前元素最小值。

维护当前区间最大值 curMax。

弹出最小值更新答案，再推进该列表指针并更新 curMax。

当某个列表耗尽时停止。

复杂度分析：

时间复杂度：O(N log k)，N 为元素总数，k 为列表数量。

空间复杂度：O(k)。

import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int curMax = Integer.MIN_VALUE;

        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            pq.offer(new int[]{val, i, 0});
            curMax = Math.max(curMax, val);
        }

        int bestL = 0;
        int bestR = Integer.MAX_VALUE;

        while (pq.size() == nums.size()) {
            int[] top = pq.poll();
            int val = top[0];
            int listIdx = top[1];
            int elemIdx = top[2];

            if (curMax - val < bestR - bestL) {
                bestL = val;
                bestR = curMax;
            }

            if (elemIdx + 1 < nums.get(listIdx).size()) {
                int nextVal = nums.get(listIdx).get(elemIdx + 1);
                pq.offer(new int[]{nextVal, listIdx, elemIdx + 1});
                curMax = Math.max(curMax, nextVal);
            } else {
                break;
            }
        }

        return new int[]{bestL, bestR};
    }
}

import "container/heap"

type item632 struct {
	val     int
	listIdx int
	elemIdx int
}

type minHeap632 []item632

func (h minHeap632) Len() int           { return len(h) }
func (h minHeap632) Less(i, j int) bool { return h[i].val < h[j].val }
func (h minHeap632) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap632) Push(x interface{}) {
	*h = append(*h, x.(item632))
}
func (h *minHeap632) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func smallestRange(nums [][]int) []int {
	pq := &minHeap632{}
	heap.Init(pq)

	curMax := -1 << 31
	for i := 0; i < len(nums); i++ {
		val := nums[i][0]
		heap.Push(pq, item632{val: val, listIdx: i, elemIdx: 0})
		if val > curMax {
			curMax = val
		}
	}

	bestL, bestR := 0, 1<<31-1
	for pq.Len() == len(nums) {
		top := heap.Pop(pq).(item632)
		if curMax-top.val < bestR-bestL {
			bestL = top.val
			bestR = curMax
		}

		if top.elemIdx+1 < len(nums[top.listIdx]) {
			nextVal := nums[top.listIdx][top.elemIdx+1]
			heap.Push(pq, item632{val: nextVal, listIdx: top.listIdx, elemIdx: top.elemIdx + 1})
			if nextVal > curMax {
				curMax = nextVal
			}
		} else {
			break
		}
	}

	return []int{bestL, bestR}
}

相似题目

题目	难度	考察点
632. 最小区间	困难	堆
23. 合并 K 个升序链表	困难	堆
373. 查找和最小的 K 对数字	中等	堆
378. 有序矩阵中第 K 小的元素	中等	堆
786. 第 K 个最小的质数分数	困难	堆
347. 前 K 个高频元素	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/61916172