解题思路
单调栈的基础应用。我们以矩形高度为单位建立一个单调不降的栈,每次输入一个新的矩形高度 h 时,如果新的高度比栈顶高度低,则一直 pop,并累计 pop 出的元素的宽度,每次 pop 我们都可以看做得到一个高度为 h,宽度为累计总宽度的一个矩形(可以看做是把这段的所有矩形高度都削减为 h),用它的面积更新答案。pop 结束后将我们最终得到的新矩形入栈即可。
参考代码
#include <cstdio>
#include <stack>
using namespace std;
struct info {
int h, w;
};
int main(int argc, char const *argv[]) {
int n, h;
while(scanf("%d", &n), n) {
stack<info> s;
long long ans = 0;
for(int i=0; i<n; ++i) {
scanf("%d", &h);
int w = 0;
while(!s.empty() && s.top().h>h) {
w += s.top().w;
ans = max(ans, 1LL*s.top().h*w);
s.pop();
}
s.push((info){h, w+1});
}
int w = 0;
while(!s.empty() ) {
w += s.top().w;
ans = max(ans, 1LL*s.top().h*w);
s.pop();
}
printf("%lld\n", ans);
}
return 0;
}
还不快抢沙发