算法基础篇（13）单调栈

1、单调栈的定义单调栈顾名思义就是具有单调性的栈。因此它依旧是一个栈结构只不过里面存储的数据是严格递增或者严格递减的。这种结构是很容易实现的如下面代码#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], 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 test2() { stackint st; for(int i 1; i n; i) { // 栈里面小于等于a[i]的元素全部出栈 while(st.size() st.top() a[i]) st.pop(); st.push(a[i]); } }那么维护一个单调栈的意义是什么2、单调栈解决的问题单调栈能帮我们解决下面四个问题·寻找当前元素左侧离它最近并且比它大的元素在哪·寻找当前元素左侧离它最近并且比它小的元素在哪·寻找当前元素右侧离它最近并且比它大的元素在哪·寻找当前元素右侧离它最近并且比它小的元素在哪。虽然是四个问题但是原理是一致的。所以只要解决一个举一反三就可以解决剩下的几个。2.1 寻找当前元素左侧离它最近并且比它大的元素在哪从左往右遍历元素构造一个单调递减的栈。插入当前元素时如果栈为空则左侧不存在比当前元素大的数如果栈非空插入当前位置元素时的栈顶元素就是所要找的元素。注意因为我们要找的是最终结果的位置。因此栈里面存的是每个元素的下标。#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], 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); } }2.2 寻找当前元素左侧离它最近并且比它小的元素在哪从左往右遍历元素构造一个单调递增的栈。插入当前元素时如果栈为空则左侧不存在比当前元素小的数如果栈非空那么栈顶元素就是要找的元素。注意因为我们要找的是最终结果的位置。因此栈里面存的是每个元素的下标。#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], 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); } }剩下两种情况原理类似只需要修改一下遍历顺序即可。2.3 寻找当前元素右侧离它最近并且比它大的元素在哪#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], n; int ret[N]; void test() { stackint st; for(int i n; i 1; i--) { while(st.size() a[st.top()] a[i]) { st.pop(); } if(st.size()) { ret[i] st.top(); } st.push(i); } }2.4 寻找当前元素右侧离它最近并且比它小的元素在哪#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], n; int ret[N]; void test() { stackint st; for(int i n; i 1; i--) { while(st.size() a[st.top()] a[i]) { st.pop(); } if(st.size()) { ret[i] st.top(); } st.push(i); } }3、单调栈的应用#include iostream #include stack using namespace std; const int N 1e6 10; typedef long long LL; int n; LL h[N], v[N]; LL sum[N]; int main() { cin n; for(int i 1; i n; i) { cin h[i] v[i]; } stackint st1; for(int i 1; i n; i) { while(st1.size() h[st1.top()] h[i]) { st1.pop(); } if(st1.size()) { sum[st1.top()] v[i]; } st1.push(i); } stackint st2; for(int i n; i 1; i--) { while(st2.size() h[st2.top()] h[i]) { st2.pop(); } if(st2.size()) { sum[st2.top()] v[i]; } st2.push(i); } LL ret 0; for(int i 1; i n; i) { ret max(ret, sum[i]); } cout ret endl; return 0; }