刷题总结
滑动窗口
单向队列queue,
#include <queue>, 仅支持插入队尾push(int i),弹出队头pop()双向队列duque,
#include<deque>, 支持插入队头push_front(int i),插入队尾push_back(int i),删除队头pop_front(),删除队尾pop_back()
对于一般的滑动窗口,如果不用pop队尾,可以用queue
queue<int> q;
// 遍历序列每个元素
for(int i = 0; i < n; i++){
// 检查新加入的元素是否满足条件,如果满足,加入队尾
if(check(q.front(), i))
q.push(i);
// 根据问题,对插入的nums[i]操作
...
// check(q.front())意为:检查队头是否满足条件,如果不满足,则弹出
while(!q.empty() && check(q.front())){
q.pop();
}
}
如果需要求滑动窗口最大最小值,可以使用deque
deque<int> q;
// 遍历序列每个元素
for(int i = 0; i < n; i++){
// 检查队头是否满足条件,如果不满足,弹出队头
while(!q.empty() && check(q.front())) q.pop_front();
// 检查队尾是否满足条件,如果不满足,弹出队尾
while(!q.empty() && check(q.back(), i)) q.pop_back(i);
// 将新元素加入队尾
q.push_back(i);
}
例如acwing 154 滑动窗口
https://www.acwing.com/problem/content/156/
#include <iostream>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, k;
int main(){
deque<int> q;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
// 求滑动窗口最小值
for(int i = 0; i < n; i++){
// 队列存储的是滑动窗口的最小值的索引
// 队列的长度不一定为k
// 窗口第一个元素的索引为idx,长度为k的窗口对应的末尾元素的索引为idx + k - 1,也为i
// 所以i = idx + k - 1 或idx = i - k + 1
// 可推出:
// (1)i = idx + k - 1:
// 所以一开始idx = 0,窗口未满,往里面填元素,当i == k - 1时,窗口刚好满;之后i > k - 1
// (2)idx = i + k - 1:
// 想要保持窗口一直为k,那么需要idx = i - k + 1 <= q.front()
// 如果i - k + 1 > q.front() 说明队头已经不在窗口内,需要弹出
// pop前保证队列不为空 且 保证窗口始终保持在k个
// 如果超出k个,说明队头需要弹出
// 如果不足或等于k个,队头也不需要弹出
while(!q.empty() && i - k + 1 > q.front()) q.pop_front();
// pop前保证队列不为空 且 如果队尾元素a[q.back()]比新元素a[i]还小
// 那么只要a[i]还在窗口内,之后窗口的最小值一定不为a[q.back()]
// 因此弹出队尾元素
while(!q.empty() && a[i] < a[q.back()]) q.pop_back();
q.push_back(i);
if(i - k + 1 >= 0)
cout << a[q.front()] << " ";
}
q.clear();
cout << endl;
// 求滑动窗口最大值
for(int i = 0; i < n; i++){
while(!q.empty() && i - q.front() + 1 > k) q.pop_front();
while(!q.empty() && a[i] > a[q.back()]) q.pop_back();
q.push_back(i);
if(i - k + 1 >= 0)
cout << a[q.front()] << " ";
}
}
当然,还可以使用双指针,只需要指向原来的数组即可
图:网格问题
网格问题
并查集
可解决图的连通分量问题