C++刷LeetCode（632. 最小区间）【滑动窗口】
本帖最后由 糖逗 于 2020-12-28 20:50 编辑题目描述：
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 比 小。
示例 1：
输入：nums = [, , ]
输出：
解释：
列表 1：，24 在区间 中。
列表 2：，20 在区间 中。
列表 3：，22 在区间 中。
示例 2：
输入：nums = [,,]
输出：
示例 3：
输入：nums = [,]
输出：
示例 4：
输入：nums = [,]
输出：
示例 5：
输入：nums = [,,,,,,]
输出：
提示：
nums.length == k
1 <= k <= 3500
1 <= nums.length <= 50
-105 <= nums <= 105
nums 按非递减顺序排列
来源：力扣（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.size(); j++){
store.push_back(make_pair(nums, 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.second;
if(temp.count(temp1) == 0 || temp == 0)count++;
temp++;
//缩小窗口
while(left < right && count == nums.size()){//在满足条件的情况下进行优化
int temp2 = store.second;
if(temp == 1)break;
temp--;
left++;
}
if(count == nums.size()&& store.first - store.first < len){
store1 = store.first;
store2 = store.first;
len = store.first - store.first;
}
//扩大窗口
right++;
}
vector<int>res = {store1, store2};
return res;
}
};
注意事项：滑动窗口要注意各个语句的前后顺序。 {:10_312:}
页:
[1]