C++刷LeetCode（632. 最小区间）【滑动窗口】

糖逗

题目描述：

1. 你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
   
2. 
   
3. 我们定义如果&#160;b-a < d-c&#160;或者在&#160;b-a == d-c&#160;时&#160;a < c，则区间 [a,b] 比 [c,d] 小。
   
4. 
   
5. &#160;
   
6. 
   
7. 示例 1：
   
8. 
   
9. 输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
   
10. 输出：[20,24]
    
11. 解释：
    
12. 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
    
13. 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
    
14. 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
    
15. 示例 2：
    
16. 
    
17. 输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
    
18. 输出：[1,1]
    
19. 示例 3：
    
20. 
    
21. 输入：nums = [[10,10],[11,11]]
    
22. 输出：[10,11]
    
23. 示例 4：
    
24. 
    
25. 输入：nums = [[10],[11]]
    
26. 输出：[10,11]
    
27. 示例 5：
    
28. 
    
29. 输入：nums = [[1],[2],[3],[4],[5],[6],[7]]
    
30. 输出：[1,7]
    
31. &#160;
    
32. 
    
33. 提示：
    
34. 
    
35. nums.length == k
    
36. 1 <= k <= 3500
    
37. 1 <= nums[i].length <= 50
    
38. -105 <= nums[i][j] <= 105
    
39. nums[i] 按非递减顺序排列
    
40. 
    
41. 来源：力扣（LeetCode）
    
42. 链接：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists
    
43. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     vector<int> smallestRange(vector<vector<int>>& nums) {
   
4.         //滑动窗口
   
5.         vector<pair<int,int> >store;
   
6.         for(int i = 0; i < nums.size(); i++){
   
7.             for(int j = 0; j < nums[i].size(); j++){
   
8.                 store.push_back(make_pair(nums[i][j], i));
   
9.             }
   
10.         }
    
11.         sort(store.begin(), store.end());
    
12.         int number_len = store.size();
    
13.         int left = 0, right = 0;
    
14.         map<int, int>temp;
    
15.         int count = 0;
    
16.         int len = INT_MAX;
    
17.         int store1, store2;
    
18.         while(right < number_len){
    
19.             int temp1 = store[right].second;
    
20.             if(temp.count(temp1) == 0 || temp[temp1] == 0)count++;
    
21.             temp[temp1]++;
    
22.             //缩小窗口
    
23.             while(left < right && count == nums.size()){//在满足条件的情况下进行优化
    
24.                 int temp2 = store[left].second;
    
25.                 if(temp[temp2] == 1)break;
    
26.                 temp[temp2]--;
    
27.                 left++;
    
28.             }
    
29.             if(count == nums.size()&& store[right].first - store[left].first < len){
    
30.                 store1 = store[left].first;
    
31.                 store2 = store[right].first;
    
32.                 len = store[right].first - store[left].first;
    
33.             }
    
34.             //扩大窗口
    
35.             right++;
    
36.         }
    
37.         vector<int>res = {store1, store2};
    
38.         return res;
    
39.     }
    
40. };

复制代码

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

糖逗