C++单调队列入门讲解及个人学习心得与总结 例题：[USACO NOV 2013银组]拥挤的奶牛 and 滑动窗口 ——求一定长度的区间内的最大值和最小值及其变式的单调队列优化

概述本文章向大家介绍C++单调队列入门讲解及个人学习心得与总结 例题：[USACO NOV 2013银组]拥挤的奶牛 and 滑动窗口 ——求一定长度的区间内的最大值和最小值及其变式的单调队列优化，主要包括C++单调队列入门讲解及个人学习心得与总结 例题：[USACO NOV 2013银组]拥挤的奶牛 and 滑动窗口 ——求一定长度的区间内的最大值和最小值及其变式的单调队列优化使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

前言

我相信你是被我优秀的标题吸引，或是想认真地学习一下单调队列的态度进来的。不管怎样，我都不会让你们失望。

先来简单介绍一下单调队列：

单调队列，从字面意思来看，即单调的队列。单调指的是这个对列的性质，那什么是单调呢？举个例子：一个序列：5 4 3 2 1我们就可以说它是单调递减的，1 2 3 4 5也是一个单调序列，不过它是单调上升的。 5 2 3 4 1显然不是；那么单调队列有什么用呢？它最重要的用途就在于可以大幅优化程序的时间复杂度，包括优化DP（多重背包。。。）。可以说，学习单调队列是对我们学习更高级算法的阶梯，也是在比赛中优化单调队列的必需品；

说了这么多，我们在来讲一下怎么维护一个队列的单调性。我们都知道，队列的特性便是先进先出，这里我们用双向队列举例子，它既可以“pop”掉队头元素，也可以pop队尾元素，相当于队列+栈。我们来看一个代码（维护一个有n个元素的队列的单调性）

for(int i=1;i<=n;i++) {//a数组为输入的元素，双向队列q

while(!q.empty() && q.back()<=a[i])//维护队列的单调性，如果队尾比当前元素小，就弹出队尾

//这样整个队列从队头到队尾都是单调下降的

q.pop_back();

q.push_back(a[i]);//插入当前元素

cout<

}

你可能会说，这并没有意义，找一个序列的最大值直接查找也能找到。确实，但在某些情况下，直接查找的复杂度是指数级的，而单调队列确实O(1)的。下面就让我们进入今天的第一题：滑动窗口.

题解

滑动窗口

洛谷 P1886 滑动窗口

题目描述

给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下图： 

 你的任务是找出窗体在各位置时的最大值和最小值。

输入

第1行：2个整数N，K(K<=N<=1000000) 第2行：N个整数，表示数组的N个元素(<=2*10^9)

输出

第1行：滑动窗口从左向右移动每个位置的最小值，每个数之间用一个空格分开 第2行：滑动窗口从左向右移动每个位置的最大值，每个数之间用一个空格分开

样例输入

8 3

1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3

3 3 5 5 6 7

此题，意思很简单就是让你求特定区间长度内的最大元素与最小元素。很容易想到爆力的解法：枚举。只需要一个i从1到n-k，再在第二重循坏循坏k次找最大元素和最小元素。但这种方法显然是不可行的，此种算法的时间复杂度为

的，可以近似理解为

,（K<=N<=1000000）。

既然这样，我们就该想想优化的算法了。来说说我一开始看到这道题的想法：枚举显然不可取；但可以先找出1-k这个区间内的最大元素和最小元素（maxi,mini）。然后i从k+1开始,当a[i]小于mini或a[i]大于maxi,就把maxi(mini)赋成a[i]，最后用数组存储起来输出；初看这个想法并没有错，时间复杂度也是O(N)的。但，这个想法却有问题，这样子做只能找到前i个数组元素的最大值，并没有考虑到区间这个要求，这时的maxi已经不起作用了，因为他已经处在这个区间之外，是无效的。

怎么改进？我们可以这样想，当这个窗口滚动时，我们把这些元素存储起来，并用上述维护单调队列的方式让这个队列是递减的。这样他的队头就是最大值。我们只需用一个while循环判断队头是否在这个区间之外，如果是就d出队列。而此时队头的元素可以保证是这个区间的最大值；

代码如下：

#include

#include

#include

using namespace std;

#define inf 0x7f7f7f7f

#define N 1000001

struct node {//单调队列的结构体

int a,num;//num为位置，用来判断是否超出区间

};

int read() {

int f=1,s=0;char a=getchar();

while(!(a>='0'&&a<='9')) {if(a=='-') f=-1 ; a=getchar(); }

while(a>='0'&&a<='9') {s=s*10+a-'0'; a=getchar();}

return f*s;

}

int k,n,t[N],p1,p2;

deque q1,q2;

int main() {

n=read();k=read();

for(int i=1;i<=n;i++)

t[i]=read();

for(int i=1;i<=n;i++) {//找区间最小值

while(!q1.empty() && q1.front().num<=i-k)//判断是否超出区间

q1.pop_front();

while(!q1.empty() && q1.back().a>t[i])//维护单调队列

q1.pop_back();

node g;

g.a=t[i];

g.num=i;

q1.push_back(g);

if(i>=k) {//输出结果

if(p1==1)

cout<<' ';

cout<

p1=1;

}

}

cout<

for(int i=1;i<=n;i++) {//找区间最大值，同上

while(!q2.empty() && q2.front().num<=i-k)

q2.pop_front();

while(!q2.empty() && q2.back().a

q2.pop_back();

node g;

g.a=t[i];

g.num=i;

q2.push_back(g);

if(i>=k) {

if(p2==1)

cout<<' ';

cout<

p2=1;

}

}

return 0;

}

拥挤的奶牛

看了滑动窗口，我们再来看看它的一道拓展题：

题目描述

FJ的n头奶牛（1<=n<=50000）在被放养在一维的牧场。第i头奶牛站在位置x(i)，并且x(i)处有一个高度值h(i)（1<=x(i),h(i)<=1000000000）。

一头奶牛感觉到拥挤当且仅当它的左右两端都有一头奶牛所在的高度至少是它的2倍，且和它的距离最多为D。尽管感到拥挤的奶牛会产生更少的牛奶，FJ还是想知道一共有多上感到拥挤的奶牛。请你帮助他。

输入

第一行：两个整数n和D。

第二行到第n+1行：每一行有两个数表示x(i)和h(i)。

输出

 一个数k表示感到拥挤的奶牛的数量。

样例输入

6 4

10 3

6 2

5 3

9 7

3 6

11 2

样例输出

2

为什么我要把这道题拿到一起讲，因为我拿到这道题时第一眼就想到了滑动窗口，它与滑动窗口十分相似，但也有些细节需要考虑；给两个提示，剩下的留给你们考虑；

1.此题需要维护两个区间的最大值；并且区间是否d出是跟据x（奶牛的位置）来的。

2.可以用两个数组来存储左边d个元素的最大值和右边d个元素的最大值。最后来比较，得出答案。

代码如下：

#include

#include

#include

#include

using namespace std;

#define N 50100

#define inf 0x7f7f7f7f

int read() {

int f=1,s=0;char a=getchar();

while(!(a>='0'&&a<='9')) {if(a=='-') f=-1 ; a=getchar(); }

while(a>='0'&&a<='9') {s=s*10+a-'0'; a=getchar();}

return f*s;

}

struct node {

int x,h;

}a[N];

bool cmp (node a,node b) {

return a.x

}

deque q1,q2;

int k,ans,max1[N],max2[N],n;

int main()

{

n=read();

k=read();

for(int i=1;i<=n;i++)

a[i].x=read(),a[i].h=read();

sort(a+1,a+1+n,cmp);

q1.push_back(a[1]);

for(int i=2;i<=n;i++) {

while(!q1.empty() && q1.front().x

q1.pop_front();

while(!q1.empty() && q1.back().h<=a[i].h)

q1.pop_back();

max1[i]=q1.front().h;

q1.push_back(a[i]);

}

q2.push_back(a[n]);

for(int i=n-1;i>=1;i--) {

while(!q2.empty() && q2.front().x>a[i].x+k)

q2.pop_front();

while(!q2.empty() && q2.back().h<=a[i].h)

q2.pop_back();

max2[i]=q2.front().h;

q2.push_back(a[i]);

}

max1[1]=max2[n]=0;

for(int i=1;i<=n;i++)

if(max1[i]>=a[i].h*2&&max2[i]>=a[i].h*2)

ans++;

cout<

return 0;

}

后记 

第二题是我们学校模拟赛的题，但当时居然忘了滑动窗口怎么打，耽误了许多时间。说明我对单调队列还不是很熟悉。

总结

以上是内存溢出为你收集整理的C++单调队列入门讲解及个人学习心得与总结 例题：[USACO NOV 2013银组]拥挤的奶牛 and 滑动窗口 ——求一定长度的区间内的最大值和最小值及其变式的单调队列优化全部内容，希望文章能够帮你解决C++单调队列入门讲解及个人学习心得与总结 例题：[USACO NOV 2013银组]拥挤的奶牛 and 滑动窗口 ——求一定长度的区间内的最大值和最小值及其变式的单调队列优化所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。