当前位置：首页 > article >正文

LeetCode 0632.最小区间：优先队列

article 2024/11/26 20:30:30

【LetMeFly】632.最小区间：优先队列

力扣题目链接：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/

你有 k 个 非递减排列 的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 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⁵ <= nums[i][j] <= 10⁵
nums[i] 按非递减顺序排列

解题方法：优先队列

使用一个优先队列，每个“整数列表”放一个元素到优先队列中，优先队列以“列表元素最小”为最优先。

优先队列中存放的，是每个列表本次要覆盖的元素。

每次从优先队列中取出一个元素：

那么这次方案(取出之前)的最小值就是取出的这个元素，最大值我们使用一个值记录并在入队时候更新。

更新最佳方案：如果当前方案优于之前的最佳方案，就更新最佳方案为这个方案。

新元素入队：如果出队元素所在列表还有新元素，则下一个元素入队，并记得更新“最大值”；否则结束循环。

时间复杂度 $O(nk\log k)$
空间复杂度 $O (k)$

AC代码

C++

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> loc(nums.size());
        auto cmp = [&nums, &loc](const int& x, const int& y) {
            return nums[x][loc[x]] > nums[y][loc[y]];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        int m = -1e8, M = -1e6;
        for (int i = 0; i < nums.size(); i++) {
            pq.push(i);
            M = max(M, nums[i][0]);
        }
        int nowm, nowM = M;
        while (pq.size()) {
            int index = pq.top();
            pq.pop();
            nowm = nums[index][loc[index]];
            loc[index]++;
            if (nowM - nowm < M - m) {
                M = nowM;
                m = nowm;
            }
            if (loc[index] == nums[index].size()) {
                break;
            }
            nowM = max(nowM, nums[index][loc[index]]);
            pq.push(index);
        }
        return {m, M};
    }
};