小旭讲解 LeetCode 632. 最小区间leetcode刷题题解

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/

小旭讲解 LeetCode 632. 最小区间leetcode刷题题解部分资料来自网络，侵权毕设源码联系删除