85. 最大矩形

思路

雖然這是一個二維矩陣的問題，但是能拆解成一系列的一維問題來想。 假設現在的矩陣是

• 第一列的高度是 $[1,0,1,0,0]$
• 第二列的高度是 $[2,0,2,1,1]$
• 第三列的高度是 $[3,1,3,2,2]$

在知道高度之後，就能夠找出從「各列看」的最大矩形面積。

如果現在給定的高度是 $[2,1,5,6,2,3]$
從 $5$ 往外擴張，

• 左邊遇到數字 $1$ 比自己小，所以左邊界在 $1$。
• 右邊遇到數字 $6$ 比自己大，繼續往右，遇到比自己小的 $2$。
  這時高度為 $5$ 的矩形面積，最大就是 $5$* (右邊界 - 左邊界 - $1$) = $10$（邊界左開右開）

如果每個數字都往外擴張去找邊界，需要花 $O(n^2)$ 的時間，因此需要優化。

優化的方式用單調棧。（紀錄位置） 以剛才的高度為例，一開始棧為空， $\text{index} = 0$， $\text{push} 2$， $\text{stk} = [0]$
$\text{index} = 1$，$\text{push} 1$，這時 $2$ 彈出，也就得知了 $2$ 的右邊界 $\text{index}$，
因為棧為空， $2$ 的左邊界是 $-1$(左開右開)，參考答案 $2 * (index - (-1) - 1) = 2$, 最後 $\text{stk} = [1]$

$\text{index} = 2$, $\text{push} 5$ 的位置，沒有彈出，$\text{stk} = [1,2]$。
$\text{index} = 3$, $\text{push} 6$ 的位置，沒有彈出，$\text{stk} = [1,2,3]$。
$\text{index} = 4$, $\text{push} 2$ 的位置，連續彈出兩次。

1. 彈出$3$(對應到 6)：
   右邊界 $\text{index} = 4$，左邊界 $\text{stk}.top() = 2$
   參考答案 $\text{heights}[3]\times(4 - 2 - 1) = 6\times 1 = 6$

2. 彈出$2$(對應到5)：
   右邊界 $\text{index} = 4$，左邊界 $\text{stk}.top() = 1$
   參考答案 $\text{heights}[2]\times(4 - 1 - 1) = 5\times 2 = 10$

後面以此類推，就能算出這一列高度的最大矩形面積。

程式碼

單調棧

class Solution {
private:
    int helper(vector<int> heights) {
        heights.push_back(0); // 加入一個 0, 方便計算
        
        int m = heights.size();
        int res = 0;
        
        stack<int> stk; // 紀錄位置        
        for(int i = 0; i < m; ++i) { // 最後的 0 會把所有的內容 pop 掉
            while(!stk.empty() && heights[stk.top()] > heights[i]) {
                int h = heights[stk.top()];
                int pos = stk.top();
                stk.pop();

                int left = stk.empty() ? -1 : stk.top(); // 左邊界
                int width = i - left - 1; // 左開右開
                res = max(res, h * width);
            }
            stk.push(i);
        }
        return res;
    }
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<int> heights(m);
        int res = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                // 如果是 1, 接續上一層, 如果是 0, 長條圖斷掉, 歸零
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0; 
            }
            res = max(res, helper(heights));
        }
        return res;
    }
};

複雜度分析

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