Leetcode: 84. Largest Rectangle in Histogram

Description

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.

Example

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

思路

• 假如已知數組為升序排列[1,2,3,5,8]
• 則結果為(1 * 5) vs (2 * 4) vs (3 * 3) vs (5 * 2) vs (8 * 1)，即通過升序方式來計算所有的面積，然後取最大值

• 使用一個棧，來維護一個升序隊列，如當前比棧頂大，直接入棧；比棧頂小，彈出並計算相應面積。註意判斷棧為空的時候，即當前元素全部彈出去後，為空，此時應該怎麼辦。

• 還有一種解釋，即使用棧維護一個升序隊列，如果當前小於棧頂，將棧頂彈出計算後，將棧頂替換為當前元素。畫個圖吧，容易理解。哈哈。

代碼

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        if(len == 0) return 0;
        
        stack<int> Stk;
        int res = -1, i = 0, index = 0, min_flag = INT_MAX;
        while(i < len){
           while(!Stk.empty() && heights[Stk.top()] > heights[i]){
               int h = heights[Stk.top()];
               Stk.pop();
               
               index = Stk.empty() ? i : i - Stk.top() - 1;
               res = max(res, h * index);
           }
           Stk.push(i);
           i++;
        }
        
    
        while(!Stk.empty()){
            int h = heights[Stk.top()];
            Stk.pop();
            index = Stk.empty() ? len : len - Stk.top() - 1;          
            res = max(res, h * index);
        }
    
        return res;
    }
};