632 最小区间

题目链接

632. 最小区间

分析

贪心 + 最小堆

由于题目所求的区间需要至少在每个区间包含一个元素，所以我们使用贪心的思想。每次计算时，仅取每个列表中最小的元素，构成一个合法的区间。那么这个区间的左右端点分别是我们取出元素的最小值和最大值。

然后我们将最小值踢出该区间，使用最小值所在的列表的下一个元素构成新的合法区间。即枚举合法区间的左端点，计算每个合法区间的长度，枚举所有区间后最短的合法区间即为答案。

考虑示例 1

$\begin{matrix} \downarrow \\ [4,& 10, & 15, & 24, & 26] \\ [0, & 9, & 12, & 20] \\ [5, & 8, & 22, & 30] \end{matrix}$

这三个列表构成的最小的合法区间即是最左侧的一列构成的区间 $[0, 4]$ ，区间的左右端点即为这一列的最大最小值。

接下来，去掉这一列中的最小值 $0$，用 $0$ 所在列表的下一个值代替

$\begin{matrix} \downarrow \\ [4,& 10, & 15, & 24, & 26] \\ [9, & 12, & 20] \\ [5, & 8, & 22, & 30] \end{matrix}$

这三个列表所构成的最小的合法区间为 $[4, 9]$，左端点为这一列元素的最小值 $4$ ，右端点为这一列元素的最大值 $9$

接下来重复操作，去掉最小值 $4$，列表变为：

$\begin{array}{llll} \ \downarrow \\ [10, & 15, & 24, & 26] \\ [9, & 12, & 20] \\ [5, & 8, & 22, & 30] \end{array}$

重复该步骤进行计算即可

所以我们维护一个最小堆来计算区间的最小值，使用一个变量来记录区间中的最大值，每次循环时，维护合法区间的最短长度即可。可以使用三元组构建堆，方便找到列表中的下一个元素；并且，在某一列表的元素已经被全部添加到堆中后，即可退出循环（之后的区间中都会缺少一个列表的元素，不为合法区间）

代码实现

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        int r = -100001;
        for(int i = 0; i < nums.size(); ++i)
        {
            pq.emplace(nums[i][0], i, 0);
            r = max(nums[i][0], r);
        }

        int ansl = get<0>(pq.top()), ansr = r;

        while(true)
        {
            auto[_, i, j] = pq.top();
            if(j == nums[i].size() - 1)
                break;

            pq.pop();
            int t = nums[i][j + 1];
            r = max(t, r);
            pq.emplace(t, i, j + 1);
            int l = get<0>(pq.top());
            if(ansr - ansl > r - l)
                ansr = r, ansl = l;
        }

        return {ansl, ansr};
    }
};

复杂度分析

• 时间复杂度：$O(n \log k)$，其中 $n$ 为 $nums$ 中所有元素的个数，$k$ 为 $nums$ 数组的长度
• 空间复杂度：$O(k)$，为小根堆使用的空间