[刷题防痴呆] 0632 - 最小区间 (Smallest Ra

题目地址

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

题目描述

632. Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

 

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

思路

• minHeap.
• 本质上是merge sort. 用heap实现.
• heap中维护一个数组, i, j, num.
• 先把每一组数的第1个放入heap中.
• 每次堆中出一个数, 更新start和end.
• 如果对应的j后面还有数, 接着放入heap中, 不停循环, 直到queue中的元素个数不为n.

关键点

• 注意, 起始的start和end要取一个合理的值.

代码

• 语言支持：Java

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int n = nums.size();
        int max = Integer.MIN_VALUE;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
        for (int i = 0; i < n; i++) {
            int num = nums.get(i).get(0);
            pq.offer(new int[]{i, 0, num});
            max = Math.max(max, num);
        }

        int start = -100000;
        int end = 100000;

        while (pq.size() == n) {
            int[] cur = pq.poll();
            int i = cur[0];
            int j = cur[1];
            int num = cur[2];

            if (max - num < end - start) {
                start = num;
                end = max;
            }

            if (j < nums.get(i).size() - 1) {
                int nextNum = nums.get(i).get(j + 1);
                pq.offer(new int[]{i, j + 1, nextNum});
                max = Math.max(max, nextNum); 
            }            
        }

        return new int[]{start, end};
    }
}