POJ-2559-Largest Rectangle in a Histogram-DP或者单调栈

Problem E

Largest Rectangle in a Histogram

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2498    Accepted Submission(s): 778

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 rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

Sample Output

8 4000

算法分析：

一个矩形只要求出高和宽就行，高即输出，我们要求就是宽，我们以一个矩形为扩展它能达到的最大宽度（由它的高所限定，两边和它能拼凑起矩形必须为连续且小于它的）

设l[i]为左边连续的不小于第i个矩形的矩形坐标点

设r[i]为右边连续的不小于第i个矩形的矩形坐标点

接下来便枚举每个矩形的高度

面积= r[i]-l[i]+1)*a[i]

单调栈栈的目的也是求l[i]和r[i],很简单看看代码就能理解。

代码实现：

#include<bits/stdc++.h>
using namespace std;
long long f,r[100001],l[100001],a[100001];
int main()
{
  while(1)
   {
       memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));

       long long n,i,j,maxx=-99999999999;
       cin>>n;
       if(n==0)  break;
       for(i=1;i<=n;i++)
           {
               cin>>a[i];
               l[i]=i;
               r[i]=i;
           }
       //两个for循环为求改点最大宽度
        for(i=2;i<=n;i++)         
        {
            j=i;
            while(j>=1&&a[i]<=a[j])  j=l[j]-1;//通过之前的l[i]结果更快地找到区间，若是直接用j--;会超时
            l[i]=j+1;                         //如果满足while就直接-1，不能确定下一个是否满足，（如果都满足，j是>=1的

        }
         for(i=n-1;i>=1;i--)
         {
             j=i;
             while(j<=n&&a[i]<=a[j])  j=r[j]+1;
             r[i]=j-1;
         }
         for(i=1;i<=n;i++)
         {
             f=(r[i]-l[i]+1)*a[i];
             maxx=max(f,maxx);
         }
         cout<<maxx<<endl;
   }
  return 0;
}

单调栈

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
typedef long long ll; 
const int N=100005;
ll h[N];
ll l[N],r[N];
int main(){
    
	int n;
	while(scanf("%d",&n)!=-1)
	{
		if(n==0) break;
		stack<ll>s;
	    for(int i=1;i<=n;i++)
	    	scanf("%lld",&h[i]);
		h[n+1]=0; ///注意这里
		for(int i=1;i<=n+1;i++)
		{
			//cout<<i<<endl;
			while(!s.empty()&&h[s.top()]>h[i])
			{
				r[s.top()]=i;
				s.pop();
			}
			if(s.size()==0)
				l[i]=0;
			else
			    l[i]=s.top();
			s.push(i);
		}
		ll ans = 0;
        for(int i=1;i<=n;i++)
            ans = max(ans,(r[i]-l[i]-1)*h[i]);
        printf("%lld\n", ans);
	}
     return 0;
 }

另一种思想的单调栈

#include<cstdio>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int MX = 100000 + 5;

int main()
{
    int N;
    int height;
    while(~scanf("%d",&N) &&N)
    {
        stack<PII>Q;
        LL ans = 0;
        for(int i=0;i<N;i++)
        {
            scanf("%d",&height);
            LL width = 0;
            while(!Q.empty() && Q.top().first>=height ){ //当栈顶元素大于当前元素
                LL tmpH = Q.top().first;
                LL tmpW = Q.top().second;
                Q.pop();width+=tmpW;//每次出栈的时候，就是计算以这个矩形的高度为最长高度的最大面积,
                //因为左边的比他小，所以只需要向右延伸就可以了
                //所以每次出栈的时候，就是出栈后的栈顶元素宽度+1
                ans = max(ans,tmpH*width);//如果大于当前的最大面积就更新
            }
            Q.push(make_pair((LL)height,(LL)width+1));
        }
        int tmp = 0;
        while(!Q.empty()){
            ans = max(ans,Q.top().first*(tmp+Q.top().second));//原理和上面一样
            tmp+=Q.top().second;Q.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}