题目点此跳转
思路
题目意思是有一个由许多矩形组成的一个图形(下底对齐)， 求这个图形里能找到的最大矩形的面积, 输入的是各个矩形的高度。 例如下图
很显然，这一题就是要求对于每一个矩形而言，它往左或右最多的比他高的矩形的个数， 也就是说，对于输入的那个数组，我们只要求出每一个元素能往左右延伸到什么地方即可，延伸的定义是不比它小的才行。 使用单调栈是解决这个问题的一个很好的办法。 我们维护一个单调栈，将数组从左到右入栈, 但是在入栈前要检查一下栈顶元素是不是比它大，如果比它大的话，说明栈顶元素就能扩展到这里了，那么就找到了栈顶元素的一个边界。 左右各扫一次就行了。 总结一句话，每次出栈的时候就是找到这个出栈元素边界的时候。
代码
LL n, a[maxn], dp[maxn], ans;
LL q[maxn], p[maxn], ft, rr;
int main() {
while(
scanf(
"%lld", &n) ==
1 && n) {
for(
int i =
1; i <= n; ++i)
scanf(
"%lld", &a[i]);
ft = rr =
0;
q[rr++] = a[
1], p[rr-
1] =
1; a[n+
1] = -
1; ans =
0;
for(
int i =
2; i <= n+
1; ++i) {
while(rr > ft && q[rr-
1] > a[i]) {
dp[p[rr-
1]] = i-p[rr-
1]; --rr;
}
q[rr++] = a[i], p[rr-
1] = i;
}
ft = rr =
0;
q[rr++] = a[n], p[rr-
1] = n; a[
0] = -
1;
for(
int i = n-
1; i >=
0; --i) {
while(rr > ft && q[rr-
1] > a[i]) {
dp[p[rr-
1]] += p[rr-
1]-i-
1; --rr;
}
q[rr++] = a[i], p[rr-
1] = i;
}
ans =
0;
for(
int i =
1; i <= n; ++i) ans = max(ans, dp[i]*a[i]);
printf(
"%lld\n", ans);
}
return 0;
}
