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.
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
8 4000
主要思路：由于每个最小单位长的矩形的高知道（即输入的数组值），那么只用计算出该位置所能向最左、最右扩展的下标的最大值就行了。最后遍历每个数据，把最右、最左值相减得到最大矩形的长，乘以对应的高就是当前数据所得到的最大矩形面积，再找出最大的那个面积就行了。对着代码动手计算一遍就明白了。
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define ll long long #define clean(arrays) memset(arrays, 0, sizeof(arrays)) ll a[100005], lefts[100005], rights[100005]; // lefts 和 rights 数组都表示的是下标 ll max_area; int main() { int n, t; while (cin>>n, n != 0) { clean(a); clean(lefts); clean(rights); for (int i = 1; i <= n; i++) cin>>a[i]; lefts[1] = 1; // 这两个是可以肯定的，赋初值 rights[n] = n; // 求a[i]左边 连续超过a[i]高度的 最远的 下标，存到 lefts 中 for (int i = 1; i <= n; i++) { t = i; while (t > 1 && a[i] <= a[t-1]) t = lefts[t - 1]; // 更新到 第t - 1 个数的下标 lefts[i] = t; } // 求a[i]右边 连续超过a[i]高度的 最远的 下标，存到 rights 中 for (int i = n - 1; i >= 1; i--) { t = i; while (t < n && a[i] <= a[t + 1]) t = rights[t + 1]; // 更新到 第t + 1 个数的下标 rights[i] = t; } max_area = -9999; for (int i = 1; i <= n; i++) { max_area = max((rights[i] - lefts[i] + 1) * a[i] , max_area); } cout << max_area << endl; } return 0; }