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: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;
    }
};

1 comment: