Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

最初很单纯的想法,对于每一个Height向左右延伸直到遇到比它矮的,然后求出此部分面积与之前最大值比较如果比最大值还大那就替代最大值,然而会因为重复计算量太大造成TLE超时。


class Solution {
public:
        int largestRectangleArea(vector<int>& heights) {
                int lp = 0, rp = 0;
                int length = 0;
                int max = 0;
                for(int i = 0; i < heights.size(); ++i)
                {
                        if(i > 0 && heights[i] == heights[i - 1]) continue;
                        if(heights[i] > 0)
                        {
                                length = 1;
                                lp = i - 1;
                                rp = i + 1;
                                while(lp >= 0 && heights[lp] >= heights[i]) { --lp; ++length; }
                                while(rp < heights.size() && heights[rp] >= heights[i]) { ++rp; ++length; }
                                if(max < heights[i] * length) max = heights[i] * length;
                        }
                }
                return max;
        }
};
TLE

然后一个优化的方法是向右找到所有符合height[i] > height[i + 1]的height,从此点向左求最大面积。因为从左到右的上坡形状上,右面永远更高,所以最大面积的宽度只可能是从高峰延伸出来的到某一点的宽度。
具体方法是从i向左回溯直到0,设回溯过程index为j,面积为j – i的最矮高度乘上(j – i + 1)


class Solution {
public:
        int largestRectangleArea(vector<int>& heights) {
                int length = 0;
                int max = 0;
                for(int i = 0; i < heights.size(); ++i)
                {
                        if(i < heights.size() - 1 && heights[i] <= heights[i + 1]) continue;
                        int tempMax = heights[i], minHeight = heights[i];
                        for(int j = i - 1; j >= 0; --j)
                        {
                                  minHeight = min(heights[j], minHeight);
                                  int temp = minHeight * (i - j + 1);
                                  if(temp > tempMax) tempMax = temp;
                        }
                        if(tempMax > max) max = tempMax;
                    }
                    return max;
          }
};
AC, 16ms

另外还有种利用stack时间复杂度O(n)的方法, 还在研究中。

Leave a Reply

Your email address will not be published. Required fields are marked *