题意

如图所示，在一条水平线上有n个宽为1的矩形，求包含于这些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。

思路

一个很老的，也是一个很好的题目。

维护一个单调栈即可。

不过在洛谷SP1805里是蓝题，还真是意外呢。

代码

#include <iostream> #include <cstdio> using namespace std; #define N 100005 struct Elem { int height; int count; }stack[N]; int top; int main() { int height, n; long long ans, tot, tmp; while (scanf("%d", &n) != EOF && n) { top = 0; ans = 0; for (int i = 0; i < n; ++i) { scanf("%d", &height); tmp = 0; while (top > 0 && stack[top - 1].height >= height) { tot = stack[top - 1].height * (stack[top - 1].count + tmp); if (tot > ans) ans = tot; tmp += stack[top - 1].count; --top; } stack[top].height = height; stack[top].count = 1 + tmp; ++top; } tmp = 0; while (top > 0) { tot = stack[top - 1].height * (stack[top - 1].count + tmp); if (tot > ans) ans = tot; tmp += stack[top - 1].count; --top; } printf("%lld\n", ans); } return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10162410.html

相关资源：电力系统接线图如图所示