LeetCode 632.最小区间

你有 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${}^5$ <= nums[i][j] <= 10${}^5$
nums[i] 按非递减顺序排列

滑动窗口，滑窗区间是所有输入数列中的最小值到最大值，窗口内包含来自所有数列的值时即找到了一个符合题意的区间，维护最小区间即可：

class Solution {
public:vector<int> smallestRange(vector<vector<int>>& nums) {unordered_map<int, unordered_set<int>> numPos;int minNum = numeric_limits<int>::max();int maxNum = 0;for (int i = 0; i < nums.size(); ++i) {minNum = min(minNum, nums[i][0]);maxNum = max(maxNum, nums[i][nums[i].size() - 1]);for (int j = 0; j < nums[i].size(); ++j) {numPos[nums[i][j]].insert(i);}}unordered_map<int, int> freq;int validListNum = 0;int left = minNum;int ansBegin = 0;int ansLen = numeric_limits<int>::max();for (int i = minNum; i <= maxNum; ++i) {for (int pos : numPos[i]) {if (++freq[pos] == 1) {++validListNum;}}while (validListNum == nums.size()) {if (i - left + 1 < ansLen) {ansBegin = left;ansLen = i - left + 1;}for (int pos : numPos[left]) {if (--freq[pos] == 0) {--validListNum;}}++left;}}vector<int> ans = {ansBegin, ansBegin + ansLen - 1};return ans;}
};

如果每个数列的平均长度为n，数列中的数字范围为m，则此算法时间复杂度为O(nk + m)，空间复杂度为O(nk)。

以上代码中，从最小值一直循环到了最大值，如果范围很大，但列表中的数字数量很小，会很耗时，因此可以把每个数字及其出现位置组成一个pair，然后放到一个vector里，这样遍历vector里的数字就可以了。