【POJ2559】Largest Rectangle in a Histogram

阳光穿透心脏的1/2处 2021-10-23 07:19 192阅读 0赞

[更好的阅读体验][Link 1]

> 参考：李煜东《算法进阶指南》

[POJ][] [洛谷][Link 2]

## 【题目】 ##

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:

![2559\_1.jpg][2559_1.jpg]

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.

#### **输入格式：** ####

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.

#### **输出格式：** ####

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.

## 【Input】 ##

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

## 【Output】 ##

8
    4000

## 【分析】 ##

其实我一开始看到题目，是想用DP的，但想状态转移方程，想着想着发现怎么越来越像单调栈解法了。。。。。。

于是，便用了单调栈。因为比较喜欢偷懒，用STL比较多，所以这里也是用的STL。

由于一个子矩形的计算高度是由最小高度决定的，所以我们假设有一段单调递增的矩形，为了求出最大子矩形面积，可以分别以每个矩形作为起始矩形计算，取出最大值。于是我们可以每次找到一段这样的矩形堆，用栈储存，如果当前矩形的高度不满足单调递增，则进行以上操作，找到小于等于它的高度的矩形为止。最后把高度为当前矩形的高度，宽度为累计宽度的矩形入栈，在继续找。

最后的最后，记得把栈中剩下的矩形拿出来计算。

为了简化程序实现，可以增加一个高度为0的矩形k\[n+1\]，避免栈中还有剩余矩形。

## 【代码】 ##

#include<cstdio> #include<stack> #define max(a,b) a>b?a:b using namespace std; struct histogram{ long long h,w; }; //h是高度，w是宽度 int n; long long sum=0,ans=0; long long k[100010]; int main(){ while(scanf("%d",&n)){ ans=0; if(n==0) break; stack<histogram>s; for(int i=1;i<=n;i++) scanf("%lld",&k[i]); k[n+1]=0; for(int i=1;i<=n+1;i++){ sum=0; while(!s.empty()&&s.top().h>k[i]){ sum+=s.top().w; ans=max(ans,sum*s.top().h); s.pop(); } s.push((histogram){k[i],sum+1}); } printf("%lld\n",ans); } return 0; }

转载于:https://www.cnblogs.com/hlw1/p/11135359.html

[Link 1]: https://komorebi.icu/2019/07/03/%E3%80%90POJ-2559%E3%80%91Largest-Rectangle-in-a-Histogram/#more
[POJ]: http://poj.org/problem?id=2559
[Link 2]: https://www.luogu.org/problemnew/show/SP1805
[2559_1.jpg]: /images/20211023/ca2be63da02a42c884f6ede00fdd44b4.png