滑动窗口问题
最小区间
题目地址力扣-最小区间(Hard)
1.滑动窗口
设置左右两个指针,新元素从右侧进入窗口,旧的元素从左侧移除窗口,根据当前窗口内的元素是否满足需求,决定窗口的扩张与收缩。
基本原理
2.问题描述
格式
样例
3.代码
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<sstream>
using namespace std;
vector<int> smallestRange(vector<vector<int> > nums)
{
//1.
///key值+value
multimap<int,int>numstomap;///记录每个数字所属的组序号,multimap允许重复的key值
for(int i=0;i<nums.size();i++)
{
for(int j=0;j<nums[i].size();j++)
{
numstomap.insert(pair<int,int> (nums[i][j],i));
}
}
//2.
int res=INT_MAX;//用来记录区间的大小,初始值为最大
int leftv=0;//返回的区间的左右值,初始化为0
int rightv=0;
unordered_map<int,int> curmap;///组序号-个数
int n=nums.size();///总组数
multimap<int,int>::iterator left = numstomap.begin();//窗口左指针
multimap<int,int>::iterator right= numstomap.begin();//窗口右指针
while(right!=numstomap.end())
{
curmap[right->second]++;//窗口扩张
while(curmap.size()==n)//说明已经找到一个可行解
{
if(right->first-left->first<res)
{
res=right->first-left->first;
leftv=left->first;
rightv=right->first;
}
//收缩窗口
curmap[left->second]--;
if(curmap[left->second]==0)
{
curmap.erase(left->second);
}
left++;
}
right++;
}
if(res==INT_MAX)
return {};
else
return {leftv,rightv};
}
int main( )
{
//知识点1:每行的元素输入个数不确定时,采用字符串流形式进行处理
int n;
cin>>n;//总行数
getchar();
string str;//以字符串形式一行行读入
vector<vector<int> >arrays;//记录所有输入的元素
for(int i=0;i<n;i++)
{
vector<int>nums;//记录每行数组
getline(cin,str);//一行读入到str中
istringstream ss(str);//将str转化为字符串流ss
int tmp;
while(ss>>tmp) //从字符串流ss中读取元素
{
nums.push_back(tmp);
}
arrays.push_back(nums);
}
vector<int>ans=smallestRange(arrays);
cout<<ans[0]<<" "<<ans[1]<<endl;
return 0;
}
4.总结
- 输入n行数据,每行的元素个数不确定且未知时,先用字符串读取一行数据,然后转化为字符串流形式进行处理参考网址
2.multimap和map的区别
总结下,就是
只有key(就用set)
存在键值对key-value,就用map
若允许key重复,则用multimap
若按照hash方式组织元素,则用unordered_map
3.注意迭代器遍历map写法
后续可以用right,left进行元素遍历,right++,left++则表示后移一位
如何理解下面一段代码是关键
//numstomap 记录数字+组号
int res=INT_MAX;//用来记录区间的大小,初始值为最大
int leftv=0;//返回的区间的左右值,初始化为0
int rightv=0;
unordered_map<int,int> curmap;///组序号-个数
int n=nums.size();///总组数
multimap<int,int>::iterator left = numstomap.begin();//窗口左指针
multimap<int,int>::iterator right= numstomap.begin();//窗口右指针
while(right!=numstomap.end())
{
curmap[right->second]++;//窗口扩张
while(curmap.size()==n)//说明已经找到一个可行解
{
if(right->first-left->first<res)
{
res=right->first-left->first;
leftv=left->first;
rightv=right->first;
}
//收缩窗口
curmap[left->second]--;
if(curmap[left->second]==0)
{
curmap.erase(left->second);
}
left++;
}
right++;
}