Leetcode 84. Largest Rectangle in Histogram

Largest Rectangle in Histogram

給定n個非負整數表示直方圖的條高，其中每個條的寬度為1，求直方圖中最大矩形的面積。

Python

使用單調棧 :

• 構建一個棧，如果當前元素比棧頂元素高，那麼將該元素入棧
  否則，依次從棧頂開始彈出元素，直到找到比當前元素小的元素，這個時候棧頂元素為形成rectangle的左邊界，當前所在位置為右邊界，這樣就可以算出當前rectangle面積
• 這樣就可以通過從前向後遍歷一遍heights就可以得到所有minarea，並從中挑出最大值
• 值得注意的有兩點：1. 棧中保存的元素為heights中相應height的index，這樣才可以一直能夠計算相應的面積2. 需要在heights後加入一個比所有height都小的值，否則的話，包括最後一個height在內的矩形面積便會被忽略

class Solution(object):
    def largestRectangleArea(self, heights):
            
        stack = []
        maxarea = 0
        heights.append(0)
        n = len(heights)
        for i in range(n):
            if not stack or heights[i]>heights[stack[-1]]:
                stack.append(i)
            else:
                while stack and heights[i]<=heights[stack[-1]]:
                    h = heights[stack[-1]]
                    stack.pop()
                    w = i if not stack else i-stack[-1]-1
                    maxarea = max(maxarea,h*w)
                stack.append(i)
        return maxarea

C++

方法一

首先找出當前區間中高度最小的柱子，然後分別對它左邊和右邊的區間遞歸求解，並取最大值。最後，我們還需要考慮包含最小柱子的矩形面積，這可以通過最小柱子的高度乘以區間長度來計算。

時間複雜度為 O(n log n)，空間複雜度為 O(log n)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        return helper(heights, 0, heights.size() - 1);
    }
    
private:
    int helper(vector<int>& heights, int left, int right) {
        if (left > right) {
            return 0;
        }
        int min_index = left;
        for (int i = left + 1; i <= right; i++) {
            if (heights[i] < heights[min_index]) {
                min_index = i;
            }
        }
        return max(heights[min_index] * (right - left + 1),
                   max(helper(heights, left, min_index - 1),
                       helper(heights, min_index + 1, right)));
    }
};

方法一

對於每個柱子，我們不斷彈出比它高的柱子，計算它們向左和向右最多能延伸多少個柱子，從而得到它們所在的矩形面積。在計算完所有矩形面積後，取最大值即可。為了方便計算，我們在高度數組末尾添加一個高度為 0 的虛擬柱子。

時間複雜度為 O(n)，空間複雜度為 O(n)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0); 
        int n = heights.size();
        stack<int> s;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                int h = heights[s.top()];
                s.pop();
                int w = s.empty() ? i : i - s.top() - 1;
                ans = max(ans, h * w);
            }
            s.push(i);
        }
        return ans;
    }
};