Largest Rectangle in a HistogramTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 12865Accepted Submission(s): 3621Problem 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 34 1000 1000 1000 10000
Sample Output
84000
Source
University of Ulm Local Contest 2003
题目链接：?pid=1506
题目大意：一排木板并排放，宽都是1，高是输入值，求所包含面积中的最大子矩形的面积
题目分析：由于本题的n比较大1e5，因此O(n^2)直接枚举的做法肯定T，我们考虑对其进行优化，对于每个木板，如果其左边或者右边的值大于等于它的值，则可以将它的左边界或右边界向左或向右延伸，这个很好理解，因为它的高度最小，，假设为h1，则以其为中心扩展出的最大的矩形面积为h1*(区间长度)
#include <cstdio>#include <cstring>#include <algorithm>#define ll long longusing namespace std;int const MAX = 100005;int h[MAX], l[MAX], r[MAX];int main(){int n;while(scanf("%d", &n) != EOF && n){h[0] = h[n + 1] = -1; //这里初始化的值必须小于0，否则因为高度可能为0，左边界数组下标可能变为－1for(int i = 1; i <= n; i++){scanf("%d", &h[i]);l[i] = r[i] = i;}for(int i = 1; i <= n; i++){while(h[i] <= h[l[i] – 1]){l[i] = l[l[i] – 1];if(h[l[i]] == 0)break;}}for(int i = n; i >= 1; i–){while(h[i] <= h[r[i] + 1]){r[i] = r[r[i] + 1];if(h[r[i]] == 0)break;}}ll ans = 0;for(int i = 1; i <= n; i++)ans = max(ans, (ll)h[i] * (ll)(r[i] – l[i] + 1));printf("%I64d\n", ans);}}
dp的路好难走，越难越要走
即使爬到最高的山上，一次也只能脚踏实地地迈一步。
