[LeetCode] Largest Rectangle in Histogram

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 height = [2,1,5,6,2,3],
return 10.

思路1：Brute Force

对每个bar i，求它能构成的最大面积。用左右指针向两边扫，直到遇到比bar i矮的或遇到边界则停止，然后根据左右指针距离得到宽度和面积。但是这个解法过不了大集合，因为最坏情况：当整个histogram是递增或递减时，算法复杂度是O(n^2)。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: int largestRectangleArea(vector<int> &height) { int maxArea = 0; for(int i=0; i<height.size(); i++) maxArea = max(maxArea, calRecArea(height,i)); return maxArea; } int calRecArea(vector<int> &height, int index) { int left = index-1, right = index+1; while(left>=0 && height[left]>=height[index]) left--; while(right<height.size() && height[right]>=height[index]) right++; return (right-left-1)*height[index]; } };

思路2：Stack

仔细考察Brute Force算法，发现问题在于指针重复扫描。以递增序列为例：

0 1 2 3 4 5 6

在计算s[0]的时候扫描了右边6个数，计算s[1]时继续扫描右边5个数，依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时，bar i~j的面积一定都能扩展到j。而一旦在j+1递减了，那么表示bar i~j中的部分bar k无法继续扩展，条件是h[k]>h[j+1]。

1. 利用这个性质，可以将递增序列cache在一个stack中，一旦遇到递减，则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k，并计算面积。

2. 由于面积的计算需要同时知道高度和宽度，所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度，而反之则不行。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int largestRectangleArea(vector<int> &height) { if(height.empty()) return 0; height.push_back(-1); height.insert(height.begin(),-1); stack<int> s; int maxArea = 0; for(int i=0; i<height.size(); i++) { while(!s.empty() && height[i]<=height[s.top()]) { int h = height[s.top()]; s.pop(); if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h); } s.push(i); } // reset height height.erase(height.begin()); height.pop_back(); return maxArea; } };