## Wednesday, November 26, 2014

### [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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19``` ```class Solution { public: int largestRectangleArea(vector &height) { int maxArea = 0; for(int i=0; i &height, int index) { int left = index-1, right = index+1; while(left>=0 && height[left]>=height[index]) left--; while(right=height[index]) right++; return (right-left-1)*height[index]; } }; ```

0 1 2 3 4 5 6

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 &height) { if(height.empty()) return 0; height.push_back(-1); height.insert(height.begin(),-1); stack s; int maxArea = 0; for(int i=0; i

#### 1 comment:

1. try 1 5 5 5 2 9 2 9 2
yours will output 15 instead of 2*8 = 16