# 每日一dp(1)——Largest Rectangle in a Histogram（poj 2559）使用单调队列优化

Largest Rectangle in a Histogram

```/************************************************************************/
/*

1. 即每次插入都从后往前找，找到不小于自己的，插入并抛弃该位置后面的数据
2. 每次都从队头取元素，并及时淘汰过期数据

q中存放的则是1.2.3.....i-1 的位置，更新的是比[i-1]大的元素，即比[i-1]大的元素都

*/
/************************************************************************/
#include <iostream>
using namespace std;
const int maxn=5+100000;
int a[maxn];
int q[maxn],l[maxn],r[maxn];
int N,tail,front;
__int64 ans,tmp;
int main()
{
int i;
while(scanf("%d",&N),N)
{
for(i=1;i<=N;i++)
scanf("%d",a+i);
tail=1;front=0;q[1]=1;
for(i=2;i<=N;i++)
{
while( front<tail && a[q[tail]]>a[i] )
r[q[tail]]=i-1,tail--;
q[++tail]=i;
}
while(front<tail)
r[q[tail]]=N,tail--;

tail=1;q[1]=N;
for(i=N-1;i;i--)
{
while( front<tail && a[q[tail]]>a[i] )
l[q[tail]]=i+1,tail--;
q[++tail]=i;
}
while(front<tail)
l[q[tail]]=1,tail--;
ans=0;
for(i=1;i<=N;i++)
{
tmp=r[i]-l[i]+1;
tmp*=a[i];
ans=ans>tmp?ans:tmp;
}
printf("%I64d\n",ans);

}
return 0;
}
```

## Largest Rectangle in a Histogram (poj 2559 &amp;&amp; hdu 1506 矩形系列 迭代法)

Language: Default Largest Rectangle in a Histogram Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 15608   Accepted: 5040 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectan

## Largest Rectangle in a Histogram HDU - 1506 （单调栈）

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the

## HDU 1506 Largest Rectangle in a Histogram （dp左右处理边界的矩形问题）

E - Largest Rectangle in a Histogram Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1506 Appoint description: Description A histogram is a polygon composed of a sequence of rectangles aligned a

## POJ 2559 Largest Rectangle in a Histogram (单调栈或者dp)

Largest Rectangle in a Histogram Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 15831   Accepted: 5121 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal wi

## HDU 1056 Largest Rectangle in a Histogram（dp）（求最大的矩形面积）

Problem Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of

## POJ2559——DP——Largest Rectangle in a Histogram

Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectang

## poj2559 Largest Rectangle in a Histogram

Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectang