小旭讲解 LeetCode 632. 最小区间

B站

原题

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

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

示例 1:

输入:[[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] 中。

注意:

给定的列表可能包含重复元素，所以在这里升序表示 >= 。
1 <= k <= 3500
$10^{-5}$ <= 元素的值 <= $10^5$

思路

重要的是，正如视频中提到的，该如何想到使用多指针的方式来解决这个题目。

将原问题转变成在 k 个列表中定位一个值，并组成集合 S。此时，自然集合中的元素是由 k 个列表中的值组成。那么当前集合 S 中的最大值与最小值的差值即为求解区间的大小。那么，当 S 中的差值最小时的长度，即为问题求解的最小区间的答案。

维护 k 个指针，指向每一个列表中第一个元素的位置。因为数组具有单调性，我们可以按照如下方式进行迭代，进而找到最小区间：

维护最小区间：k 个指针指向的元素中的最小值与最大值之差
将最小值所在的位置向右移动
当某一个指针超出所在列表长度时，跳出循环

代码

vector<vector<int>> _nums;
struct cmp{
    bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
        return _nums[a.first][a.second] > _nums[b.first][b.second];
    }
};
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        // 4 10 15
        // 0 9 12
        // 5 18 22
        // 最小堆 {4, 0, 5} -> {4, 9, 5}
        //                 -> {10, 0, 5}
        _nums = nums;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
        int ma = -1e5, l = -1e5, r = 1e5;
        for (int i = 0; i < nums.size(); ++i) {
            pq.push({i, 0});
            ma = max(ma, nums[i][0]);
        }
        while (true) {
            auto pa = pq.top();
            pq.pop();
            if (ma - nums[pa.first][pa.second] < r - l) {
                l = nums[pa.first][pa.second], r = ma;
            }
            if (++pa.second >= nums[pa.first].size()) break;
            pq.push(pa);
            ma = max(ma, nums[pa.first][pa.second]);
        }
        return {l, r};
    }
};

复杂度分析

时间复杂度： $O(k * n * logk)$ n 为列表平均长度，k 为列表个数
空间复杂度： $O(k)$

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-632-smallest-range-covering-elements-from-k-lists/