算法基础篇（13）单调栈

1、单调栈的定义

单调栈，顾名思义，就是具有单调性的栈。因此，它依旧是一个栈结构，只不过里面存储的数据是严格递增或者严格递减的。这种结构是很容易实现的（如下面代码）

#include <iostream> #include <stack> using namespace std; const int N = 3e6 + 10; int a[N], n; // 维护一个单调递增的栈 void test1() { stack<int> 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() { stack<int> 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() { stack<int> 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() { stack<int> 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() { stack<int> 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() { stack<int> 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]; } stack<int> 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); } stack<int> 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; }