84. 柱狀圖的最大矩形

思路

跟 907. 子數組的最小值之和 一樣，將思路逆轉過來。
假如現在柱狀圖是 $heights=[2,1,5,6,2,3]$ ，此時想要找高度為 5 的最大矩形面積，要怎麼做？
是不是也是要往左邊找邊界，往右邊找邊界，假如遇到比自己小的，矩形的高度就不能維持 5 了？ 之所以要往兩邊找，是因為這樣才能讓寬度最大，進而讓面積最大， 所以，同樣的，對於數字 5，要找到左 / 右邊比自己小，最近的數字的位置left，right。 對於 $heights[2]=5$ 來說：

• height[left] = height[1] = 1
• height[right] = height[4] = 2 此時的寬度是right - left - 1，開區間。

程式碼

1. 單調棧

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {    
        heights.push_back(0); // 加入一個 0, 方便計算
        int n = heights.size();
        int res = 0;
        stack<int> stk;
        for(int i = 0; i < n; i++) { 
            while(!stk.empty() && heights[stk.top()] > heights[i]) {
                int h = heights[stk.top()]; stk.pop();
                int left = stk.empty() ? -1 : stk.top(); // 左邊界
                int width = i - left - 1; // 左開右開
                res = max(res, h * width);
            }
            stk.push(i);
        }
        // 最後的 0 會把所有的內容 pop 掉，不需要清空棧
        return res;
    }
};

2. 陣列模擬棧

class Solution {
private:
    static const int MX = 1e5 + 1;
    int stk[MX];
public:
    int largestRectangleArea(vector<int>& heights) {    
        heights.push_back(0); // 加入一個 0, 方便計算
        int n = heights.size();
        int j = -1; // 指向棧頂的位置
        int res = 0;
        stack<int> stk;
        for(int i = 0; i < n; i++) {
            while(j >= 0 && heights[stk[j]] > heights[i]) {
                int h = heights[stk[j]]; j--;
                int left = j >= 0 ? -1 : stk[j]; // 左邊界
                int width = i - left - 1; // 左開右開
                res = max(res, h * width);
            }
            stk[++j] = i;
        }
        // 最後的 0 會把所有的內容 pop 掉，不需要清空棧
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$