单调栈学习总结

单调栈就是一个栈里面要么全放升序的值，要么全是降序的值。

可以做下这道题加深理解：HDU 1506

题解可以看“李二娃的博客”，里面有详细的debug过程，很直观。

https://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

HDU 1506 AC代码：

#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
const int maxn = 500010;
typedef long long ll;
ll a[maxn];
ll max(ll x,ll y){
    if(x >= y) return x;
    else return y;
}
int main()
{
    int n;
    while(scanf("%d",&n) == 1){
        if(n == 0) break;
        stack<ll> st;
        for(int i = 0;i < n;i++){
            scanf("%lld",&a[i]);
        }
        a[n] = 0;
        ll ans = 0;
        for(int i = 0;i <= n;i++){
            while(!st.empty() && a[st.top()] > a[i]){
                int cur = st.top();st.pop();//这里一定要先pop
                ans = max(ans,a[cur]*(st.empty() ? i : (i-st.top()-1)));
            }
            st.push(i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*

*/