Hard

题目描述

给定 k 个按非递减顺序排列的整数列表，找到包含每个列表中至少一个数字的最小区间。

我们定义区间 [a, b] 比区间 [c, d] 更小，当且仅当 b - a < d - c 或者在 b - a == d - c 时 a < c。

示例 1：

输入：nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

提示：

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -10^5 <= nums[i][j] <= 10^5
  • nums[i] 按非递减顺序排列

解题思路

这道题的核心思路是使用滑动窗口结合最小堆来解决。我们需要找到一个最小区间，使得每个列表中都至少有一个元素在这个区间内。

算法思路：

  1. 初始化：为每个列表维护一个指针，初始都指向第一个元素。使用最小堆存储当前每个列表指向的元素及其所属列表信息。

  2. 滑动窗口策略：当前区间的左边界是堆顶元素（最小值），右边界是当前所有指针指向元素的最大值。

  3. 窗口移动：每次移动最小元素所在列表的指针，这样可以尝试缩小区间。同时更新最大值和最优解。

  4. 终止条件：当某个列表的指针超出范围时停止，因为此时无法保证每个列表都有元素在区间内。

这种方法的优势在于：

  • 利用了每个列表已排序的特性
  • 通过最小堆高效维护当前最小值
  • 滑动窗口确保每次都尝试最优的移动策略

时间复杂度主要来自堆操作，每个元素最多进出堆一次，总体效率较高。

代码实现

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();
        vector<int> indices(k, 0);
        vector<int> result = {0, INT_MAX};
        
        while (true) {
            int minVal = INT_MAX, maxVal = INT_MIN, minIdx = 0;
            
            for (int i = 0; i < k; i++) {
                if (indices[i] == nums[i].size()) {
                    return result;
                }
                
                if (nums[i][indices[i]] < minVal) {
                    minVal = nums[i][indices[i]];
                    minIdx = i;
                }
                maxVal = max(maxVal, nums[i][indices[i]]);
            }
            
            if (maxVal - minVal < result[1] - result[0]) {
                result[0] = minVal;
                result[1] = maxVal;
            }
            
            indices[minIdx]++;
        }
        
        return result;
    }
};

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        import heapq
        
        k = len(nums)
        heap = []
        max_val = float('-inf')
        
        # 初始化堆，每个列表的第一个元素入堆
        for i in range(k):
            heapq.heappush(heap, (nums[i][0], i, 0))
            max_val = max(max_val, nums[i][0])
        
        result = [heap[0][0], max_val]
        
        while heap:
            min_val, list_idx, element_idx = heapq.heappop(heap)
            
            # 更新最小区间
            if max_val - min_val < result[1] - result[0]:
                result = [min_val, max_val]
            
            # 如果当前列表还有下一个元素
            if element_idx + 1 < len(nums[list_idx]):
                next_val = nums[list_idx][element_idx + 1]
                heapq.heappush(heap, (next_val, list_idx, element_idx + 1))
                max_val = max(max_val, next_val)
            else:
                # 某个列表已经遍历完，无法继续
                break
        
        return result

public class Solution {
    public int[] SmallestRange(IList<IList<int>> nums) {
        int k = nums.Count;
        var heap = new SortedSet<(int val, int listIdx, int elemIdx)>();
        int maxVal = int.MinValue;
        
        // 初始化堆
        for (int i = 0; i < k; i++) {
            heap.Add((nums[i][0], i, 0));
            maxVal = Math.Max(maxVal, nums[i][0]);
        }
        
        int[] result = {heap.Min.val, maxVal};
        
        while (heap.Count > 0) {
            var min = heap.Min;
            heap.Remove(min);
            
            // 更新最小区间
            if (maxVal - min.val < result[1] - result[0]) {
                result[0] = min.val;
                result[1] = maxVal;
            }
            
            // 移动指针
            if (min.elemIdx + 1 < nums[min.listIdx].Count) {
                int nextVal = nums[min.listIdx][min.elemIdx + 1];
                heap.Add((nextVal, min.listIdx, min.elemIdx + 1));
                maxVal = Math.Max(maxVal, nextVal);
            } else {
                break;
            }
        }
        
        return result;
    }
}

var smallestRange = function(nums) {
    const heap = [];
    let max = -Infinity;
    
    // Initialize heap with first element from each list
    for (let i = 0; i < nums.length; i++) {
        heap.push([nums[i][0], i, 0]);
        max = Math.max(max, nums[i][0]);
    }
    
    // Build min heap
    heap.sort((a, b) => a[0] - b[0]);
    
    let result = [heap[0][0], max];
    let minRange = max - heap[0][0];
    
    while (true) {
        // Extract min
        const [val, listIdx, elemIdx] = heap.shift();
        
        // If we can't advance this list, we're done
        if (elemIdx + 1 >= nums[listIdx].length) break;
        
        // Add next element from same list
        const nextVal = nums[listIdx][elemIdx + 1];
        max = Math.max(max, nextVal);
        
        // Insert into heap maintaining order
        let insertPos = 0;
        while (insertPos < heap.length && heap[insertPos][0] <= nextVal) {
            insertPos++;
        }
        heap.splice(insertPos, 0, [nextVal, listIdx, elemIdx + 1]);
        
        // Update result if we found smaller range
        const newMin = heap[0][0];
        const newRange = max - newMin;
        if (newRange < minRange || (newRange === minRange && newMin < result[0])) {
            result = [newMin, max];
            minRange = newRange;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
滑动窗口 + 最小堆O(n * log k)O(k)

其中 n 是所有列表元素总数，k 是列表个数。时间复杂度主要来自堆操作，每个元素最多进出堆一次。空间复杂度为堆的大小。

相关题目