最优美的算法之一 —— 单调队列
应用
在了解单调队列之前,我们可以看一看有关单调队列的应用
给定一个长度为n的数组,给定一个k,使得在[i, i + k]这样的区间内的,分别输出的这个区间内的最大值和最小值。
如果是暴力思维的话,那么就可以直接遍历这里面所有的n,找到里面的最小的数和最大的数。
代码的话就是这样
n, m = map(int,input().split())#python version
maxn = []
minn = []
num = list(map(int,input().split()))
for i in range(0, n - m + 1):
maxn.append(max(num[i:i + m]))
minn.append(min(num[i:i + m]))
for i in range(len(minn)):
print(minn[i],end=" ")
print("")
for i in range(len(minn)):
print(maxn[i],end=" ")
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
// const INF = 0x3f3f3f;
int a[N];
int n, k;
void get_max()
{
for(int i = 1; i <= n - k + 1; i++)//遍历获得每个子区间内的最大值
{
int maxx = a[i];
for(int j = 0; j < k; j ++)
{
maxx = max(maxx, a[i + j]);
}
cout << maxx << " " ;
}
}
void get_min()
{
for(int i = 1; i <= n - k + 1; i++)//遍历获得每个自区间的最小值
{
int minn = a[i];
for(int j = 0; j < k; j ++)
{
minn = min(minn, a[i + j]);
}
cout << minn << " " ;
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout .tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
get_min();
cout << endl;
get_max();
return 0;
}
很显然,我们能够证明这样的算法复杂度是O(n * k)
这显然并不是一个很好的实现的方式,但是似乎没有什么好的方法,
这个时候就可以使用单调队列的思想
实现
一,我们以图中的数据为例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y8EHFGOV-1630999333074)(…/…/…/图片/QQ截图20210907150847.png)]
我们是要将这个队列初始化
使得在【0, k - 1】内里面的第一位一定是这个数组内的最小的数
int head = 0, tail = 0;
for(int i = 1; i < k; i++)
{
while(head <= tail && a[q[tail]] >= a[i]) tail--;//使得入队的结果的一定是前面结果里面最小的
q[++tail] = i;
}
二,然后就可以从【k, n】的过程完成遍历,
出队的结果有且仅有两种
①,这个最小值不在这个区间内
②,这个数已经不是最小值了
代码的实现为
for(int i = k; i <= n; i++)
{
while(head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
while(q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
综合起来,代码的实现就是
#include<iostream>
using namespace std;
const int N = 1e6 + 3;
int q[N], a[N];
int n, k;
void get_min()
{
int head = 0, tail = 0;
for(int i = 1; i < k; i++)
{
while(head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
}
for(int i = k; i <= n; i++)
{
while(head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
while(q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
void get_max()
{
int head = 0, tail = 0;
for(int i = 1; i < k; i++)
{
while(head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
}
for(int i = k; i <= n; i++)
{
while(head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
while(q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
get_min();
puts("");
get_max();
return 0;
}
复杂度为O(n),大大的优化了。