C++ 单调栈原理与模板

单调栈就是具有单调性的栈他依旧是一个栈结构只不过里面的数据是递增或递减的严格的增或减模板如下#include iostream#include stackusing namespace std;const int N 3e6 10;int a[N];int n;void test1(){stackint st;// 维护一个单调递增的栈for(int i 1; i n; i){//栈里面大于等于a[i] 的元素全部出栈while(st.size() st.top() a[i]) st.pop();st.push(a[i]);}}void text2(){stackint st; // 维护一个单调递减的栈for(int i 1; j n; i){//栈里面小于等于a[i] 的元素全部出栈while(st.size() st.top() a[i]) st.pop();st.push(a[i]);}}int main(){text1();text2();return 0;}单调栈解决的问问题寻找当前元素左侧理它最近并且比他大的元素在哪寻找当前元素左侧理它最近并且比他小的元素在哪寻找当前元素右侧理它最近并且比他大的元素在哪寻找当前元素右侧理它最近并且比他大的元素在哪寻找当前元素左侧理它最近并且比他大的元素在哪寻找当前元素左侧理它最近并且比他大的元素在哪从左往右遍历元素构造一个单调递减的栈插入当前我位置的元素如果栈为空则左侧不存在比当前元素大的元素如果栈为非空则插入当前位置时的栈顶元素就是所要找的元素注意因为我们要找的是最终结果因此栈里面存在每个元素的下标代码的实现单调递减的栈 左边const int n 1e5 10;int n;int a[N];int ret[N];void test(){stackint st; // 单调递减的栈for(int i 1; i n; i){while(st.size() a[st.top()] a[i]) st.pop();if(st.size()) ret[i] st.top(); //下标st.push(i);}for(int i 1; i n; i)cout ret[i] ;cout endl;}int mian(){cin n;for(int i 1; i n; i){cin a[i];}test();return 0;}单调递增的栈 左边#include iostream#include stackusing namespace std;const int n 1e5 10;int n;int a[N];int ret[N];void test(){stackint st; // 单调递增的栈for(int i 1; i n; i){while(st.size() a[st.top()] a[i]) st.pop();if(st.size()) ret[i] st.top(); //下标st.push(i);}for(int i 1; i n; i)cout ret[i] ;cout endl;}int mian(){cin n;for(int i 1; i n; i){cin a[i];}test();return 0;}右边 单调递减的栈const int n 1e5 10;int n;int a[N];int ret[N];void test(){stackint st; // 单调递减的栈for(int i 1; i n; i){while(st.size() a[st.top()] a[i]) st.pop();if(st.size()) ret[i] st.top(); //下标st.push(i);}for(int i n; i 1; i--)cout ret[i] ;cout endl;}int mian(){cin n;for(int i 1; i n; i){cin a[i];}test();return 0;}右边 单调增的栈const int n 1e5 10;int n;int a[N];int ret[N];void test(){stackint st; // 单调递增的栈for(int i 1; i n; i){while(st.size() a[st.top()] a[i]) st.pop();if(st.size()) ret[i] st.top(); //下标st.push(i);}for(int i 1; i n; i)cout ret[i] ;cout endl;}int mian(){cin n;for(int i n; i 1; i--){cin a[i];}test();return 0;}