LintCode 122: Largest Rectangle in Histogram (單調遞增棧經典題!)

1. 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.

Example

Given height = [2,1,5,6,2,3],

return 10.

思路：單調遞增棧。

這題實際上等價于:對每個矩形求左右最近的一個比他低的矩形的邊界，然後左右兩側距離相加(還要-1，因為自身算了2遍)×該矩形高度。然後找出所有矩形中該操作的最大值。

注意：

1. 為什麼是單調遞增棧而不是單調遞減棧?

   因為對棧top矩形來說，我們要找左右兩邊最近的比他低的矩形。我們從左到右掃描，如果新的矩形比top矩形低，則新的矩形是top矩形的右邊最近的比它低的元素。同時，top矩形在棧内的下面一個矩形是其左邊離它最近的低的元素。

2. 時間複雜度O(n)。因為每個元素入棧出棧一次。

3. 注意w = s.empty() ? i : i - s.top() - 1。

   這裡首先要注意stack可能會empty，如果是，則直方圖寬度為i。

   若否，則直方圖寬度為i-s.top()-1，因為直方圖的右邊界為i - 1，左邊界為s.top()+1，是以寬度為(i-1)-(s.top()+1)+1=i-s.top()-1。

   注意這裡的s.top()已經更新了，它實際上是pop()掉的那個s.top()的下面一個。

4. 最右邊加一個dummy，確定最後一個矩形也被考慮。但要注意for循環裡面是<=len，因為加了一個dummy, 實際len的值加了1。

5. while循環裡面用>=和>都可以，效果是等價的。

   例如，nums=[5,5,5,5,5]，用>=的話每個5都會挨個挨個pop掉，用>的話，所有的5是到最後一步才逐個pop掉。但效果是一樣的。

代碼如下：

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        int len = height.size();
        if (len == 0) return 0;
        
        int maxArea = 0;
        vector<int> height2 = height;
        height2.push_back(-1);
        
        stack<int> monoIncStack; // mono increasing stack

        for (int i = 0; i <= len; ++i) {
            while(!monoIncStack.empty() && 
                  (height2[monoIncStack.top()] >= height2[i])) {
                
                int top = monoIncStack.top();
                monoIncStack.pop();
                int h = height2[top];
                int w = monoIncStack.empty() ? i : i - monoIncStack.top() - 1; 
                //note it is not i - top - 1;
            
                maxArea = max(maxArea, h * w);
            }
            
            monoIncStack.push(i);
        }
        
        return maxArea;
    }
};
           

這題也可以在數組兩邊各加一個dummy，這樣就不用判斷stack.empty()了。這裡要注意data.size()已經加了2。代碼如下:

int LargestRec2(vector<int> &data) {
    stack<int> monoStack; //單調遞增棧
    int maxV = 0;

    //add two dummy boundaries
    data.insert(data.begin(), -1);
    data.push_back(-1);

    for (int i=0; i<data.size(); ++i) {
        while(!monoStack.empty() && data[monoStack.top()]>data[i]) {
            int oldTop = monoStack.top();
            monoStack.pop();
            maxV = max(maxV, data[oldTop]*(i-monoStack.top()-1));
        }
        monoStack.push(i);
    }

    return maxV;
}