计算最大矩形面积|计算最大矩形面积,POJ(2082) 计算最大矩形面积|POJ(2082)

题目链接：http://poj.org/problem?id=2082
把矩形按照高度一次递增的循序排列，当违反这一规则的时候，更新ans,用新的data替换之前的矩形。然后最后扫一遍。
【计算最大矩形面积|计算最大矩形面积,POJ(2082)】
文章图片

文章图片

文章图片

#include #include #include using namespace std; struct rec { int w; ///宽 int h; ///高 } data; int main() { int n; while(scanf("%d",&n),n!=-1) { int ans=0; int totalw=0; ///总宽 int curarea=0; ///当前面积 stack s; ///定义一个长方形的栈 int lasth=0; ///上一次进栈的矩形的高度 for(int i=0; i=lasth) { s.push(data); } else { ///更新ans totalw=0; curarea=0; while(!s.empty()&&s.top().h>data.h) { totalw+=s.top().w; curarea=totalw*s.top().h; if(curarea>ans) ans=curarea; s.pop(); ///抛掉,最后用新的data代替 } totalw+=data.w; data.w=totalw; s.push(data); } lasth=data.h; }totalw=0; ///总宽度 curarea=0; ///当前面积 while(!s.empty()) { totalw+=s.top().w; curarea=totalw*s.top().h; if(curarea>ans) ans=curarea; s.pop(); } printf("%d\n",ans); } return 0; }

View Code
转载于:https://www.cnblogs.com/TreeDream/p/5483542.html