55. Largest Rectangle in Histogram

题意

给一个包含n个非负数的数组，表示n个宽度为1的直方柱，求可以用长方形圈出来的最大面积。

思路1：

以上图为例，我们用一个res表示目前得到的最大面积，首先第一次扫描数组，获得最矮直方体1，res=1*6。
然后若获得比这个面积大的面积，肯定是要剔除该高度为1的直方柱。故求1左面和1右面，递归。

int func(vector<int>& heights, int left, int right) {
	if (left == right) return heights[left];
	if (left > right) return 0;

	int minv = INT_MAX, minn = left;
	for (int i = left; i <= right; ++i) {
		if (minv > heights[i]) {
			minv = heights[i];
			minn = i;
		}
	}
	return max({ minv*(right - left + 1),func(heights,left,minn - 1),func(heights,minn + 1,right) });
}
int largestRectangleArea(vector<int>& heights) {
	return func(heights, 0, heights.size() - 1);
}

思路2：

遍历数组，每次都向左向右找到连续的不高于该柱体的范围，求得面积。

int largestRectangleArea(vector<int>& heights) {
	int sz = heights.size(), res = INT_MIN, left, right;
	if (sz == 0)
		return 0;
	if (sz == 1)
		return heights[0];
	for (int i = 0; i < sz; ++i) {
		left = right = i;
		while (left > 0 && heights[left - 1] >= heights[i])
			--left;
		while (right <sz - 1 && heights[right + 1] >= heights[i])
			++right;
		if (heights[i] * (right - left + 1) > res)
			res = heights[i] * (right - left + 1);
	}
	return res;
}

思路3：利用栈，我没看懂

http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html