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