【朝夕的ACM笔记】数据结构-单调栈 - 网站源码_资源分享

【相抱的ACM讲义】产品目录与检索

死板栈

甚么是死板栈

死板栈是栈计算机程序的一类形变，在满足用户栈科天料（FILO）的前提下，更要满足用户栈内原素遵从死板性。比如说从栈底到args原素维持递减的死板递减栈。

怎样保护死板栈

以保护两个死板递减栈为例。

当填入两个新原素时，为的是保护栈内的死板性，他们将该原素与args原素展开较为，若不满足用户死板性，就将args原素弹出，急速多次重复，直至栈空或是满足用户死板性年末，最终再将该原素插进args。

写出标识符是这模样：

for(int i=1;i<=n;i++) { while(!sta.empty()&&sta.top()>=a[i]) sta.pop(); sta.push(a[i]); }//c++ stl版for(int i=1;i<=n;i++) { while(top>0&&sta[top]>=a[i]) top—; sta[++top]=a[i]; }//数组版

当然，实际上他们更常用的是用死板栈保存原素的下标，而非其值——

for(int i=1;i<=n;i++) { while(!sta.empty()&&a[sta.top()]>=a[i]) sta.pop(); sta.push(i); }//c++ stl版for(int i=1;i<=n;i++) { while(top>0&&a[sta[top]]>=a[i]) top—; sta[++top]=i; }//数组版

死板栈的应用

死板栈最经典的应用，是在两个数列里寻找距离原素最近的比其大/小的原素位置。

比如说以下问题：

对数列中的每个原素，寻找其左侧第两个比它大的原素位置。

显而易见的，他们可以遍历每个原素，然后从其位置往左寻找，这样的暴力做法时间复杂度是 $O(n2)$ O(n^2) 。

但死板栈可以将时间复杂度降到 $O(n)$ O(n) ——

他们只需从右往左遍历数列，依次将原素加入死板栈中，保护两个从栈底到args递减的死板栈；

当某个原素被从栈内弹出时，代表它遇到了两个比它更大的原素，因为是从右往左遍历，所以该原素是第两个比它大的原素，即所求。

如果最终仍在栈内，则说明该原素左侧没有比它更大的原素。

遍历的时间复杂度是 $O(n)$ O(n)，每个原素最多被加入死板栈一次、弹出来一次，所以总时间复杂度是 $O(n)$ O(n) 。

对于要求解的这类问题，他们可以列两个简单的表格——

求解的问题遍历方向保护死板性（栈底->args）左侧第两个更大从右到左死板递减左侧第两个更小从右到左死板递减右侧第两个更大从左到右死板递减右侧第两个更小从左到右死板递减

拓展内容：怎样寻找左侧第二个比当前原素大的原素位置？

注：以下内容都是个人想法，仅供参考。

这个问题源自于本人在打比赛时遇到的一道题——

其题目大意是这样：一列人在排队，身高有高有矮，每个人可以插队无限次比自己矮的人，仅可以插队一次比自己高的人，问如果只有两个人插队，这个人最多能排到多前面？

答案实际上是左侧第二个比当前原素大的原素位置+1。

但问题是，要怎样求解呢？

用死板栈可以简单快速求解出第两个，但第二个却并不能直接用死板栈求解。

他们可能会想到，保护两个死板栈！

当原素被第两个死板栈弹出时，塞进第二个死板栈，当其再次被弹出时遇到的是答案。

但第二个死板栈的死板性就不能简单粗暴地去保护，而需要一些技巧——

因为栈科天料的特性，他们需要把取出的原素先塞进两个临时栈，然后再从临时栈塞进第二个死板栈，以维持其死板性。

每个原素最多被插进三次栈，弹出三次栈，总时间复杂度依旧是 $O(n)$ O(n) 的，当然，常数可能较为大。

参考标识符：

#include<bits/stdc++.h>#define ll long long #define pb push_back#define sz size() #define pii pair<int,long long> #define mkp make_pair using namespace std; const int N=1e6+10; stack<int>st1,st2,st3; int a[N],ans[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>=1;i—) { while(!st2.empty()&&a[st2.top()]<a[i]) { ans[st2.top()]=i+1; st2.pop(); } while(!st1.empty()&&a[st1.top()]<a[i]) { st3.push(st1.top()); st1.pop(); } st1.push(i); while(!st3.empty()) st2.push(st3.top()),st3.pop(); } while(!st1.empty()) ans[st1.top()]=1,st1.pop(); while(!st2.empty()) ans[st2.top()]=1,st2.pop(); for(int i=1;i<=n;i++) cout<<ans[i]<<endl; return 0; }