题目大意:
给出一个整数n,表示有n个宽为1的矩形。紧接着输入n个整数,表示每个矩形的高,要求输出最大连续矩形的面积。
思路:
单调栈。
代码:
#include<iostream> #include<stdio.h> #include<stack> using namespace std; struct point //将矩形的高度和位置封装在结构体中。 { int val; //矩形高度的值。 int pos; //pos表示矩形在序列中的位置。 }height[100001]; int main() { int n; while(scanf("%d",&n)&&n) { stack<point> s; for(int i=0;i<n;i++) { scanf("%d",&height[i].val); height[i].pos=i; } height[n].val=0; height[n].pos=n; //使用height[n]的目的是使下面的循环可以在单调递增序列下正常求取面积。 s.push(height[0]); long long max=0; for(int i=1;i<=n;i++) { while(s.size()&&height[i].val<=s.top().val) //在栈不为空的情况下,判断当前矩形的高是否小于等于栈顶矩形的高。 { long long area=(long long)s.top().val*(long long)(i-s.top().pos); max=max>area?max:area; height[i].pos=s.top().pos; //这一步很微妙,要了解单调栈在本题中的几何意义。 //循环里的这几步操作实际上相当于将矩形i重新放置到左边第一个比它小的矩形前, //并计算矩形i右边第一个矩形到循环开始前的栈顶矩形的最大连续面积。 //而对矩形i的放置操作就体现在了对height[i].pos的更改上。 s.pop(); } s.push(height[i]); } printf("%I64d\n",max); } }