題目描述:給定一個僅含 '0' 和 '1' 的二維矩陣,求只包含 '1' 的最大矩形面積。
解題思路:將問題轉化為「直方圖中最大矩形面積」(LeetCode 84)逐行處理。
第一步:建立高度直方圖
維護一個長度為 cols 的陣列 heights,對每一行 row:若 matrix[row][col] == '1',則 heights[col] += 1;否則 heights[col] = 0。這樣每個 heights[col] 就代表以當前行為底、向上連續 '1' 的高度。
第二步:對每行的直方圖求最大矩形 使用單調遞增堆疊(Monotonic Stack):
0 可簡化清理邏輯。每行執行一次直方圖求最大矩形,最終取所有行中的最大值即為答案。
時間複雜度:O(rows × cols) — 外層迴圈遍歷每一行(O(rows)),每行更新高度陣列 O(cols) 並執行單調棧求直方圖最大矩形 O(cols),整體為 O(rows × cols)。
空間複雜度:O(cols) — 高度陣列與單調棧均最多儲存 cols 個元素,不需要額外的矩陣空間。
1. Initialize heights[0..cols-1] = 0.
2. Initialize maxArea = 0.
3. For each row r from 0 to rows-1:
a. For each col c: heights[c] = (matrix[r][c]=='1') ? heights[c]+1 : 0.
b. Run largestRectangleInHistogram(heights):
i. Initialize empty stack stk.
ii. For i from 0 to cols (inclusive, with sentinel h=0 at i=cols):
- While stk not empty AND heights[stk.top()] > h:
height = heights[stk.pop()]
width = stk.empty() ? i : i - stk.top() - 1
maxArea = max(maxArea, height * width)
- Push i onto stk.
c. Update maxArea with result of step b.
4. Return maxArea.方法一:純動態規劃(left / right / height 陣列)
對每個位置 (r, c) 維護三個陣列:height[c](向上連續 1 的高度)、left[c](在目前高度下可延伸的最左邊界)、right[c](最右邊界)。每行 O(cols) 更新三個陣列,面積 = height[c] * (right[c] - left[c])。時間複雜度 O(rows × cols),空間複雜度 O(cols),無需堆疊,實作略複雜但全為陣列操作,快取友好。
方法二:暴力枚舉(三層迴圈)
固定矩形的上邊界 r1 和左右邊界 c1, c2,掃描從 r1 向下每一行判斷 [c1, c2] 是否全為 '1',更新最大面積。時間複雜度 O(rows² × cols²),空間複雜度 O(1)。僅適用於小規模輸入,面試中作為暴力出發點說明優化方向。
left 和 right 陣列的更新順序(left 從左到右、right 從右到左)有何重要性?若順序錯誤會導致什麼問題?