你有 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里的數字就可以了。