5 条题解
信息
- ID
- 65
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 287
- 已通过
- 128
- 上传者
这道题大意就是让我们求区间内的最大最小值,就是一道RMQ问题,可以用单调队列解决。
单调队列,顾名思义就是一个所有元素都有单调性的队列,我们可以建立一个队列来维护这些数据。
首先每加入新元素前,我们要检查队首是否还在需统计的区间中,若否,出队。
其次,维护队列单调性。以区间最大值为例,如果当前元素比队尾元素大,就不停出队,直到元素不大于队尾元素为止。
处理完后,区间的最大值就是队首元素,直接输出即可。
以下为部分代码,为防止复制就没全贴上来了(笑):
//区间最小值
for(int i=1;i<=n;i++){
while(!q.empty()&&i-k>=q.front()){
q.pop_front();
}//检查队首是否还在需统计的区间中
while(!q.empty()&&a[i]<=a[q.back()]){
q.pop_back();
}//维护队列单调性
q.push_back(i);
if(i>=k){
cout<<a[q.front()]<<" ";
}//输出
}
cout<<endl;
q.clear();//一定要清空,因为你接下来还有算区间最大值