http://www.Sina.com/http://www.Sina.com /
名词的解释
实现
功能
例题
为了理解名词的解释是什么是单调堆栈，我们可以分开理解什么是“单调”，什么是“堆栈”。
栈首先引入百度百科中栈的定义
堆栈(stack )别名被称为堆栈，是运算受到限制的线性表。 限制只在页脚中进行插入和删除操作的线性表。 这一端称为堆栈顶，而另一端称为堆栈底。 在堆栈中插入新元素也称为堆栈、堆栈或推式堆栈。 这是将新元素放在堆栈的顶层元素上，使其成为新堆栈的顶层元素。 从堆栈中删除元素(也称为堆栈或转义)是删除堆栈的顶级元素，使相邻元素成为新堆栈的顶级元素。
用自己的话来说，堆栈是数据结构，其主要特征是先进的后起之秀。
堆栈的具体操作在此不详细叙述。
单调的小学五年级学生知道单调是什么意思。
被称为单调递增函数的递增函数；被称为单调递减函数的递减函数。 两者统称为单调函数。
在这里，单调是指增加或减少。
单调堆栈是指该堆栈中的元素单调。 从下向上要么单调增加，要么单调减少。
实现单调堆栈其实很简单，以单调增长的堆栈为例：
假设现在有7种元素，分别是69791048。
那么，首先进入堆栈的是元素6，先进入堆栈。
还有要素9，96。 因为正在制作单调增加的堆栈，所以9也要进入堆栈。
然后7进来了。 7小于9，所以为了形成单调增加的堆栈，必须去掉9。
而且堆栈内还有6，7大于6，为了形成单调递增堆栈，直接将7放入堆栈中。
那么，现在堆栈内的情况如下。
后面的元素9大于7，所以直接进入堆栈。
然后的元素10大于9，所以就这样进入堆栈。
堆栈中的情况如下图所示。
下面的元素是4，4先与堆栈顶部的元素10相比，10大于4，所以10离开堆栈。
然后，将10个堆栈后的堆栈顶部元素9进行比较，9仍然大于4，因此9个堆栈。
比较此时的堆栈顶部元素7，7还是大于4，所以7发出堆栈。
之后，与此时的堆叠顶部单元6相比较，由于6大于4，所以也出现堆叠。 但是，由于此时堆栈已经为空，所以将4放入堆栈中。
还有另一个元素8、8大于堆栈顶部元素4，所以8进入堆栈。 最后一个堆栈中的情况如下图所示
所以，要实现单调的堆栈，其实只是判断、堆栈、堆栈入三个步骤。
知道功能如何实现单调堆栈后，我们能在单调堆栈上做什么呢？
首先考虑一个问题。 实现单调堆栈时，最重要的部分是哪里？ 判断堆栈中的元素是否可以进行堆栈以使其单调。
是的，我们必须操作的部分是判断。
当新元素准备进入堆栈时，我们会将其确定为堆栈的顶级元素。 如果该元素进入堆栈后单调性受损，我们的步骤是继续将堆栈的顶层元素从堆栈中提取出来，在新元素进入堆栈后继续保持堆栈中元素的单调性。
我认为堆栈顶部的元素破坏堆栈中元素的单调性这一矛盾是单调堆栈功能的所在。
这样，使用单调堆栈可以在连续的数列中找到破坏单调性的点。
例如，在一组数据8 3 51 9中，必须找到从左边数起第一个大于的数据。
我们可以用最愚蠢的方法，使用两个for循环。 这样做需要o ()的时间复杂性。
for(intI=1； in； I ) { bool f=false； for(intj=I1； j=n； j () if ) a[j]a[I] ) { couta[j]'n '； f=真； 布雷克； }if (！ f ) cout0(n )； }很容易看出，用单调堆栈实现时，可以达到o(n )的时间复杂度。
我们制作单调减少的堆栈，保持单调减少。 当出现破坏单调性的元素，即大于堆栈顶部元素的元素时，该选项处于启用状态
始比较。如栈顶的元素比新元素小，则这个新元素就是这个栈顶元素左边的第一个比它大的数。然后这个栈顶元素就找到答案了，就出栈，然后再比较下一个栈顶元素。用样例8 3 5 1 9，一开始栈内维护着“8 3”，5比3大，则5是3左边第一个比它大的元素，出栈。然后比较5和8，因为比5大的有可能比8大，并且要维持一个单调递减的栈，则5入栈。1也类似，则此时栈内元素为“8 5 1”。当9要来时，9比此时的栈顶元素1大，9就是第一个比它大的数，然后1出栈。随后比较5，最后比较8，都和元素1一样的结果，所以最后就解决了问题。
这个问题也是洛谷里单调栈的模板题。
例题 洛谷P5788模板题
这题就是一个单调栈的模板题，找每个元素左边第一个比它大的元素的下标。
#include<iostream>#include<stack>using namespace std;const int oo=3000005;int n,a[oo],f[oo];stack<int> s;void read_in(){ios::sync_with_stdio(false),cin.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) f[i]=i;}void work(){for(int i=1;i<=n;i++){if(s.empty() || a[s.top()]>a[i]) s.push(i);else{while(!s.empty() && a[s.top()]<a[i]){f[s.top()]=i;s.pop();}s.push(i); } }while(!s.empty()){f[s.top()]=0;s.pop();}for(int i=1;i<=n;i++) cout<<f[i]<<' ';}int main(){read_in();work();return 0;} 洛谷P2947这题也是找左边第一个比它高的牛，也是一样的。
#include<iostream>#include<stdio.h>#include<stack>using namespace std;const int oo=100005;int n,a[oo],ans[oo];stack<int> s;void read_in(){ios::sync_with_stdio(false),cin.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];}void work(){for(int i=1;i<=n;i++){if(s.empty() || a[s.top()]>=a[i]) s.push(i);else{while(!s.empty() && a[s.top()]<a[i]){ans[s.top()]=i;s.pop();}s.push(i); } }for(int i=1;i<=n;i++) cout<<ans[i]<<'n';}int main(){read_in();work();return 0;} SP1805经典的矩阵面积覆盖问题。
这道题我们可以理解为，找以目前这个数为最小值，左边第一个比它小的数的位置和右边第一个比它小的数的位置。以这个数为最小值能组成的最大矩阵面积就是这两者之间的距离为底，目前的数值为高的矩形的面积。然后再比较所有答案的最大值。
#include<iostream>#include<stdio.h>#include<stack>using namespace std;stack<int> s;const int oo=100005;int n;long long l[oo],r[oo],a[oo],ans,A;void read_in(){ans=-1;for(int i=1;i<=n;i++){cin>>a[i];l[i]=r[i]=i;}}void work(){for(int i=1;i<=n;i++){if(s.empty() || a[s.top()]<a[i]){s.push(i); }else{while(!s.empty() && a[s.top()]>a[i]){l[i]=l[s.top()];r[s.top()]=i-1;s.pop();}s.push(i); }}while(!s.empty()){r[s.top()]=n;s.pop();}for(int i=1;i<=n;i++) ans=max(ans,(r[i]-l[i]+1)*a[i]);}int main(){while(cin>>n){if(n==0) break;read_in();work();if(A!=0) cout<<'n';cout<<ans;A++;}return 0;} 洛谷P1823这题很让我头疼，因为这个涉及了新元素与栈顶元素相同时的处理问题。具体是什么问题大家可以做做看。我用STL的stack做超时最后几个点了，然后找到了4年前自己还不会STL时用数组模拟栈的程序，A掉了。下面贴超时的程序供大家思考和改进。（其实是我改不出2333希望有大佬捞我一把）
#include<iostream>#include<stdio.h>#include<stack>using namespace std;const int oo=500005;stack<int> s;int n;long long a[oo],ans,same;void read_in(){ios::sync_with_stdio(false),cin.tie(0); cin>>n;for(int i=1;i<=n;i++) cin>>a[i];}void work(){for(int i=1;i<=n;i++){if(s.empty()){s.push(i); continue;}if(a[s.top()]>a[i]){ans++;s.push(i); }else{while(!s.empty() && a[s.top()]<a[i]){ans++;s.pop();}long long same=0;while(!s.empty() && a[s.top()]==a[i]){ans++;same++;s.pop();}if(!s.empty()) ans++;for(int j=1;j<=same;j++) s.push(i); s.push(i); }}cout<<ans;}int main(){ read_in();work();return 0;}
本人不才，单调栈只能稍微总结到这，如果有什么问题不懂，可以问问我，我会尽力回答。如果文章有什么问题或者我有表达错的地方，也希望能够指出。
谢谢大家，共同努力进步。