算法日记9：SC61滑动窗口(单调队列)
一、题目：
二、题解
题意为：给定一个区间长度，让你求区间长度中的最大值和最小值
- 首先，我们可以考虑用维护一个队列，用来求这个长度的最大/最小值，因此我们考虑可以使用双向队列
deque
1、我们可以用以下的步骤来实现这个功能:（以最大值举例）
- 1）：队头–>用来滑动窗口的，比如：当遍历到
i==4且k==3时，此时队头不合法，我们就应该把i==1的索引给删去，也就是front_pop()， - 2）：队尾–>用来维护单调性的，比如：假设我们要求一个最大值，当
a[i]>=a[dq.back()]那么我们就应该让队尾弹出，也就是dq.back_pop()
2、求解最大值代码如下
deque<int>dq; //用来存储最大值的下标
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (dq.size()&& dq.front()<i-k+1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
dq.pop_front();
}
//2、队尾的优越性
while (dq.size() && a[dq.back()] <= a[i]) //如果队列非空，并且此时队列的值<=即将插入的值-->把这个值弹出
{
dq.pop_back();
}
dq.push_back(i); //把值插入
if (i >= k) cout << a[dq.front()] << ' ';
}
PS:注意应该要当i>=k时，再输出a[dq.front()]，此时才能保证已经遍历到了第一个窗口
3、求解最小值代码如下
其实代码和最小值没有本质差别，只需要改变队尾的优越性判断即可
注意：此时需要把dq清空，因为求解最大值结束之后队列可能不为空
dq = deque<int>(); //清空dq，用来存储最小值的下标
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (dq.size() && dq.front() < i - k + 1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
dq.pop_front();
}
//2、队尾的优越性
while (dq.size() && a[dq.back()] >= a[i]) //如果队列非空，并且此时队列的值>=即将插入的值-->把这个值弹出
{
dq.pop_back();
}
dq.push_back(i); //把值插入
if (i >= k) cout << a[dq.front()] << ' ';
}
- 1）：队头–>用来滑动窗口的，比如：当遍历到
i==4且k==3时，此时队头不合法，我们就应该把i==1的索引给删去，也就是front_pop()， - 2）：队尾–>用来维护单调性的，比如：假设我们要求一个最小值，当
a[i]<=a[dq.back()]那么我们就应该让队尾弹出，也就是dq.back_pop()
三、完整代码如下（deque）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int a[N];
void solve()
{
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
deque<int>dq; //用来存储最大值的下标
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (dq.size()&& dq.front()<i-k+1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
dq.pop_front();
}
//2、队尾的优越性
while (dq.size() && a[dq.back()] <= a[i]) //如果队列非空，并且此时队列的值<=即将插入的值-->把这个值弹出
{
dq.pop_back();
}
dq.push_back(i); //把值插入
if (i >= k) cout << a[dq.front()] << ' ';
}
cout << '\n';
dq = deque<int>(); //清空dq，用来存储最小值的下标
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (dq.size() && dq.front() < i - k + 1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
dq.pop_front();
}
//2、队尾的优越性
while (dq.size() && a[dq.back()] >= a[i]) //如果队列非空，并且此时队列的值>即将插入的值-->把这个值弹出
{
dq.pop_back();
}
dq.push_back(i); //把值插入
if (i >= k) cout << a[dq.front()] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1; //cin >> _;
while (_--) solve();
system("pause");
return 0;
}
当然，我们也可以使用数组来模拟双向队列
四、使用数组来模拟双向队列代码如下：
4.1：改动的地方
deque<int>-->int dq[N],hh=0,tt=-1while (dq.size()&& dq.front()<i-k+1)–>while (hh<=tt && dq[hh]<i-k+1)while (dq.size() && a[dq.back()] <= a[i])–>while (hh<=tt && a[dq[tt]] <= a[i])- 最小值求解同理不再赘述
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int a[N];
int dq[N],hh=0,tt=-1;
void solve()
{
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (hh<=tt && dq[hh]<i-k+1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
hh++;//弹出队头
//dq.pop_front();
}
//2、队尾的优越性
while (hh<=tt && a[dq[tt]] <= a[i]) //如果队列非空，并且此时队列的值<=即将插入的值-->把这个值弹出
{
tt--; //弹出队尾
//dq.pop_back();
}
dq[++tt]=i; //把下标插入
if (i >= k) cout << a[dq[hh]] << ' ';
}
cout << '\n';
hh=0,tt=-1; //清空dq，用来存储最小值的下标
for (int i = 1; i <= n; i++)
{
//1、队头的合法性
while (hh<=tt && dq[hh]<i-k+1) //如果队列非空，并且有在窗口之外的数-->把这个数pop
{
hh++;//弹出队头
//dq.pop_front();
}
//2、队尾的优越性
while (hh<=tt && a[dq[tt]] >= a[i]) //如果队列非空，并且此时队列的值<=即将插入的值-->把这个值弹出
{
tt--; //弹出队尾
//dq.pop_back();
}
dq[++tt]=i; //把下标插入
if (i >= k) cout << a[dq[hh]] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1; //cin >> _;
while (_--) solve();
system("pause");
return 0;
}