本文共 4065 字，大约阅读时间需要 13 分钟。
单调栈与单调队列初步应用
一、单调栈
能解决的问题：
单调栈适用于解决以某个值为最大值（最小值）为边界的最大区间问题（划重点）
使用的算法：
如果需要求解以某个值为最大值（最小值）为边界的最大区间，我们可以设想，构造一个单调递减（增）的栈，这样做的理由是单调递减（增）说明一开始的值是栈内的最大值（最小值），如果我需要求某一个值作为边界的最大区间，只需要以这个值为右边界（左边界），然后放心大胆的向左（右）拓展，直到扩展到栈的最底部，即是最大区间！
详细的算法分析：
第一：如何维护单调栈（这里我们以单调递增栈为例）
如果碰到的当前元素，比栈顶元素大，则入栈，因为这样不破坏单调性，之所以是和栈顶去比较，因为单调递增栈中的栈顶元素一定是栈中元素的最大值，比最大值还要大，添加进去肯定就不会破坏单调性啦！
第二：如何计算最大区间
当我们碰到一个会破坏单调性的元素时，此时这个元素不能压入栈中，只能从栈顶开始依次出栈，然后拿栈顶的值，向左拓展，不断计算并且维护全局最大值即可。但是，出栈究竟是出到什么时候为止呢？为了维护单调性，那自然是出栈直到把该元素压栈之后不会破坏单调性为止。这样说可能有点绕，我画个图给大家看：
字写的丑哈，大家见谅！ 第三步：如何向右边拓展并维护全局最大值
这里我就以一个简短的核心代码向大家展示：
if(h[s.top()] > h[i]){ while(!s.empty() && h[s.top()] > h[i]){ int index = s.top(); s.pop(); if(!s.empty()) area = h[index] * (i - s.top() - 1); else area = h[index] * i; maxv = area > maxv ? area : maxv; }} 我们先来解读一下上述代码：
第一步：
首先我们向右拓展，都是先确定当前的元素值，值得注意的是，我们单调栈存储的是元素的下标而不是值，因为值可能重复而下标与值是一一对应。我们先记录当前需要向右拓展的元素下标：index，然后先把栈顶 pop 处理，然后拿栈顶元素值乘以可拓展的宽度，即是能够拓展的最大区间！
第二步：
但是还是要考虑另外一种极端的情况：完全逆序！！！
设想，如果是完全逆序，我们每次入栈的元素都会破坏单调性，所以每入一个元素之前都需要出一个元素，这样我们的栈永远都只有一个元素，无法按照之前的算法去计算最大区间！ 不过，我们也可以这样去想，如果是完全逆序，那么对于任何一个元素，之前的所有元素都比它大，这样我们就可以一直向左拓展直到第一个元素的下标，也就是拓展宽度为 i ！第四步：处理冗余在栈中的其他元素
这个很简单，在一般情况下，我们按照上述的方法计算完之后是不能处理掉全部的元素的，肯定会有元素的剩余，这个大家手动模拟一下很快就能发现，小良就不多做解释了，处理该问题的代码：
while(!s.empty()){ int index = s.top(); s.pop(); if(!s.empty()) area = h[index]*(n - s.top() - 1); else area = h[index]*n; maxv = max(maxv, area); } 和之前的一样，就不多做解释了。
例题1：
图示如下：
算法分析：
为了得到最大的矩形面积，实际上就是在计算以某一个值为最小值的最大区间，或者可以理解为，只要右侧高度不断递增，那这个面积就可以不断变大，所以这显然是一个单调递增栈的问题。
由于这个矩形高度的最小值是0，所以这里有个小技巧：在预处理的时候，压入一个 -1 入栈，这样就可以保证所有的元素都能出栈，因为第一个元素会大于等于0，递增！AC代码：
#include#include #include #define LL long longusing namespace std;const int maxn = 1e5 + 5;LL n, maxv, area, h[maxn], i;int main(){ while(~scanf("%lld",&n) && n){ stack s; for(i = 0;i < n;i++) scanf("%lld",&h[i]); for(int i = 0;i < n;i++){ while(!s.empty() && h[s.top()] > h[i]){ int index = s.top(); s.pop(); if(!s.empty()) area = h[index]*(i - s.top() - 1); else area = h[index]*i; maxv = max(maxv, area); } s.push(i); } while(!s.empty()){ int index = s.top(); s.pop(); if(!s.empty()) area = h[index]*(n - s.top() - 1); else area = h[index]*n; maxv = max(maxv, area); } printf("%lld\n",maxv); maxv = 0; } return 0;}
例题2：学校OJ 1248
图示：
题意及算法分析：
这个题要求在某一块的右侧开始倒水，能够完全覆盖的木板的数量之和为多少。
我们分析一下，如果要想在右侧倒水，要能完全覆盖右边的木板，说明右边的木板比当前木板矮！如果右边的木板都比当前矮，那么这些木板的数目都可以加起来。可是算法上如何设计呢？ 我们可以维护一个单调递减栈，如果能一直递减，说明能一直覆盖，一旦出现某一个木板破坏了单调性，我们就可以以当前木板为参考，不断向左拓展，然后再维护全局最大值即可。AC代码如下：
#include#include #include #define LL long longusing namespace std;const int maxn = 1e7 + 5;struct Node{ int high, id;};LL n, ans;int main(){ scanf("%lld",&n); stack s; Node x; for(int i = 1;i <= n;i++){ scanf("%lld",&x.high); x.id = i; while(!s.empty() && s.top().high <= x.high){ ans += i - s.top().id - 1; s.pop(); } s.push(x); } while(!s.empty()){ ans += n - s.top().id; s.pop(); } printf("%lld",ans); return 0;}
二、单调队列
队列是一种要求尾部进入头部出来的线性数据结构，我们可以设想为去食堂打饭，先来的人先去打饭，后来的人老老实实在后面排队站着。而所谓单调队列，就需要维护整个队列的单调性，那究竟是如何维护单调性的呢？
数据结构分析：
如果当前来的元素，符合单调性，就让这个元素从尾部进入，如果不符合单调性呢？就和上述的单调栈一样的，让队尾的元素从尾部出去，一直到恢复单调性为止！大家可能会感到惊讶，这个维护单调队列的方法，居然要从尾部出元素，这样好像不符合队列的结构啊！所以在使用单调队列的时候，我们需要应用另外一种更加先进的队列：双端队列
双端队列
头文件：
#include
声明单调队列：
dequedq;
单调队列的基础应用：学校OJ 1249 滑动窗口
先给出一道题来看看吧：
这个所谓的最大邻域显著度，实际上指的是一维空间的某个点的 1 邻域中最大值与最小值的差值！ 算法分析：
为了求出这个邻域的最大值与最小值，我们可以把这个问题抽象化处理：
设定一个长度为 k 的滑动窗口，每次都只是在这个窗口之中查找最大值与最小值！方案一：暴力法
我们可以两次遍历，对于每一个元素都去遍历它的邻域，这样的复杂度是：O(n * k);
方案二：单调队列
单调队列可以维护一个全局的最大（最小）队首，相应的需要构造并且维护一个单调递减（增）队列！所以这道题需要用两种单调队列分别求出邻域的最大值和最小值。
做个示例：利用单调递减队列求滑动窗口最大值
void getMax(){ for(int i = 0;i < n;i++){ if(q1.empty() || a[q1.back()] >= a[i]) q1.push_back(i); else{ while(!q1.empty() && a[q1.back()] < a[i]) q1.pop_back(); q1.push_back(i); while(q1.front() < i - k + 1) q1.pop_front(); } if(i >= k - 1){ maxv[s++] = a[q1.front()]; //printf("%d ",a[q1.front()]); } }// 单调递减队列求最大值 } 那么就可以用同样的方法去解决滑动窗口最大值的问题，希望大家自己独立去完成哦！
转载地址：http://ljmq.baihongyu.com/