最大矩形

问题描述

给一个直方图，求直方图中的最大矩形的面积。
例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

Input

输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 ≤ n ≤ 100000. 然后接下来n个整数h1, ..., hn, 满足 0 ≤ hi ≤ 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

Output

对于每组测试数据输出一行一个整数表示答案。

Sample

Input: 
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Output: 
8
4000

Limitation

Time limit		1000 ms
Memory limit	32768 kB

解题思路

直方图的矩形面积 = (右端点 - 左端点) × 限制高度，每次维护一个左端点和右端点，用最小高度计算矩形面积，暴力做法就是对于每一个柱形图往左&往右找第一个小于他的高度的左/右端点，得到宽度，再乘上高度就能更新最大面积，时间复杂度为O(n²)，显然后面会超时。

这里就要用到单调栈。

每次维护矩形的左右端点的高度，利用单调非增栈，开始遇到矮的就弹栈，否则入栈并一直更新右端点，这样就能在线性时间内找到第一个比当前元素小的右端点高度，每一次弹栈的过程中更新矩形的最大面积。

这题比较要注意的就是后面 h 会很大，面积可能会超出int的范围，所以高度和面积的数据类型要用long long。

源代码

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

const int MaxN = 1e5 + 5;

struct rec {
	long long height;
	int left;
	rec() { height = 0; left = 0; }
	rec(long long h, int l) :height(h), left(l) {  }
};

int main() {
	int n;
	while (!(cin >> n).eof()) {
		if (n == 0)
			break;
		rec arr[100005];
		for (int i = 0; i < n; i++) {
			long long h;
			cin >> h;
			rec r(h, i);
			arr[i] = r;
		}
		long long ans = 0;//答案
		stack<rec> st;//栈
		rec temp;
		st.push(arr[0]);
		for (int i = 1; i < n; i++) {
			int l = arr[i].left;//矩形的右端点
			while (!st.empty() && st.top().height > arr[i].height) {
                //遇到了矮的 开始弹栈
				temp = st.top();
				st.pop();
				arr[i].left = temp.left;//更新左端点
				long long sq = (l - temp.left) * temp.height;//计算面积
				ans = max(sq, ans);
			}
			st.push(arr[i]);
		}

		while (!st.empty()) {
            //最后清栈
			temp = st.top();
			st.pop();
			long long sq = (n - temp.left) * temp.height;
			ans = max(sq, ans);
		}
		cout << ans << endl;
	}
	return 0;
}