1.何为单调栈
满足单调性的栈结构
2. 如何使用栈结构
将一个元素插入栈中时，为了维护栈的单调性，需要保障将该元素插入栈顶以后
栈满足单调性的前期下弹出最少的元素。
例如：栈中自顶向下的元素依次为 1 3 5 10 30 50，插入20时为了满足单调性，需要
依次弹出1 3 5 10，操作后栈变为 20 30 50.
使用伪码描述:
1 insert x
2 while !sta.empty() && sta.top <x
3 sta.pop()
4 sta.push(x)
#include<iostream> #include<stack> using namespace std; const int N = 100010; int stk[N], tt; int main(){ int n; cin>>n; while(n--){ int x; cin>>x; while(tt && stk[tt]>=x) tt--; (tt==0) ? cout<<"-1"<<" " : cout<<stk[tt]<<" "; stk[++tt] = x; } return 0; }
使用STL:
1 #include<iostream> 2 #include<stack> 3 using namespace std; 4 5 stack<int> s; 6 int main(){ 7 int n; 8 cin>>n; 9 while(n--){ 10 int x; cin>>x; 11 while(!s.empty() && s.top() >= x) 12 s.pop(); 13 if(s.empty()) cout<<"-1 "; 14 else cout<<s.top()<<" "; 15 s.push(x); 16 } 17 return 0; 18 }
原文：https://www.cnblogs.com/wsl96/p/13089822.html
