本文共 981 字，大约阅读时间需要 3 分钟。
挨个给n个矩形的宽和高，求内部矩形的最大面积
单调栈，每次tmp记录出栈的总宽度。记录到下一次出栈要增加的宽度。
#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 5e4 + 10;struct Squere{ int _w; int _h;}squ[MAXN];int main(){ int n; while (scanf("%d", &n)) { if (n == -1) break; for (int i = 1;i <= n;i++) scanf("%d%d", &squ[i]._w, &squ[i]._h); stack r; int res = 0; for (int i = 1;i <= n;i++) { int tmp = 0; while (!r.empty() && r.top()._h > squ[i]._h) { Squere f = r.top(); r.pop(); res = max(res, f._h * (f._w + tmp)); squ[i]._w += f._w; tmp += f._w; } r.push(squ[i]); } while (!r.empty()) { Squere f = r.top(); r.pop(); res = max(res, f._h * f._w); if (!r.empty()) r.top()._w += f._w; } printf("%d\n", res); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10606792.html