https://www.acwing.com/problem/content/133/
单调栈的模板题，按道理悬线dp不用的话也可以这样做。
需要注意这道题不能直接dp，比如[3,5,4]，这组数据，3可以拓展5，但5不能拓展4，不过3可以拓展4。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; ll a[100005]; int l[100005]; int r[100005]; stack<int> st; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku while(~scanf("%d", &n)) { if(n == 0) break; for(int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); } for(int i = 1; i <= n; ++i) { while(st.size() && a[i] < a[st.top()]) { r[st.top()] = i - 1; st.pop(); } st.push(i); } while(st.size()) { r[st.top()] = n; st.pop(); } for(int i = n; i >= 1; --i) { while(st.size() && a[i] < a[st.top()]) { l[st.top()] = i + 1; st.pop(); } st.push(i); } while(st.size()) { l[st.top()] = 1; st.pop(); } ll ans = 0; for(int i = 1; i <= n; ++i) { ans = max(ans, 1ll * a[i] * (r[i] - l[i] + 1)); } printf("%lld\n", ans); } }AcWing - 131 - 直方图中最大的矩形 = 单调栈
标签：
原文地址：https://www.cnblogs.com/Inko/p/11663222.html