51nod 1102 面积最大的矩形(单调栈)
程序员文章站
2022-11-08 22:10:22
51nod 1102 面积最大的矩形(单调栈)
以i所指的矩形高度作为要组成的矩形的高度,分别向左右扩展。用单调栈维护一个left数组和一个right数组,记录向左右能扩展到的边界,然后扫一遍出结果...
51nod 1102 面积最大的矩形(单调栈)
以i所指的矩形高度作为要组成的矩形的高度,分别向左右扩展。用单调栈维护一个left数组和一个right数组,记录向左右能扩展到的边界,然后扫一遍出结果。
#include #include #include using namespace std; const int maxn = 5e4+10; long long num[maxn]; int lt[maxn],rt[maxn]; int main() { int n; cin >> n; num[1] = 0; for(int i = 2; i <= n+1; ++i) cin >> num[i]; num[n+2] = 0; n += 2; stack s1,s2; for(int i = 1; i <= n; ++i) { while(s1.size() && num[s1.top()] >= num[i]) s1.pop(); if(s1.size()) lt[i] = s1.top()+1; else lt[i] = i; s1.push(i); } for(int i = n; i >= 1; --i) { while(s2.size() && num[s2.top()] >= num[i]) s2.pop(); if(s2.size()) rt[i] = s2.top()-1; else rt[i] = i; s2.push(i); } long long res = 0; for(int i = 1; i <= n; ++i) res = max(res,(rt[i]-lt[i]+1)*num[i]); cout << res << endl; return 0; }