C++刷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]
示例 3：

输入：nums = [[10,10],[11,11]]
输出：[10,11]
示例 4：

输入：nums = [[10],[11]]
输出：[10,11]
示例 5：

输入：nums = [[1],[2],[3],[4],[5],[6],[7]]
输出：[1,7]
 

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        //滑动窗口
        vector<pair<int,int> >store;
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums[i].size(); j++){
                store.push_back(make_pair(nums[i][j], i));
            }
        }
        sort(store.begin(), store.end());
        int number_len = store.size();
        int left = 0, right = 0;
        map<int, int>temp;
        int count = 0;
        int len = INT_MAX;
        int store1, store2;
        while(right < number_len){
            int temp1 = store[right].second;
            if(temp.count(temp1) == 0 || temp[temp1] == 0)count++;
            temp[temp1]++;
            //缩小窗口
            while(left < right && count == nums.size()){//在满足条件的情况下进行优化
                int temp2 = store[left].second;
                if(temp[temp2] == 1)break;
                temp[temp2]--;
                left++;
            }
            if(count == nums.size()&& store[right].first - store[left].first < len){
                store1 = store[left].first;
                store2 = store[right].first;
                len = store[right].first - store[left].first;
            }
            //扩大窗口
            right++;
        }
        vector<int>res = {store1, store2};
        return res;
    }
};

注意事项：滑动窗口要注意各个语句的前后顺序。

糖逗