給定一個只含
'0'與'1'的二維矩陣，找出只由'1'組成的最大矩形面積。
Example:
Input: matrix = [[“1”,“0”,“1”,“0”,“0”], [“1”,“0”,“1”,“1”,“1”], [“1”,“1”,“1”,“1”,“1”], [“1”,“0”,“0”,“1”,“0”]] Output: 6（第 2、3 列中間那塊 3×2）
Intuition
TIP
核心思路：把問題降一維——逐列累積「以該列為底、往上連續 1 的高度」形成直方圖，每列都套用 84 題「直方圖中最大矩形」。
- 對每一列，
heights[j]= 該欄往上連續'1'的數量（遇'0'歸零） - 對每列的
heights求直方圖最大矩形 → 取所有列的最大值 - 直方圖最大矩形用單調堆疊
O(n)
Approaches
⭐ 1. Per-Row Histogram + Monotonic Stack — O(m·n) / O(n)
- Idea: 把每列看成柱狀圖底邊，沿用 84 的單調堆疊解
- Time:
O(m·n)- 每列O(n)，共 m 列 - Space:
O(n)- heights 與堆疊
class Solution {
fun maximalRectangle(matrix: Array<CharArray>): Int {
if (matrix.isEmpty()) return 0
val n = matrix[0].size
val heights = IntArray(n)
var maxArea = 0
for (row in matrix) {
for (j in 0 until n) {
heights[j] = if (row[j] == '1') heights[j] + 1 else 0
}
maxArea = maxOf(maxArea, largestRectangle(heights))
}
return maxArea
}
// 84 題：直方圖中最大矩形
private fun largestRectangle(heights: IntArray): Int {
val stack = ArrayDeque<Int>() // 索引，對應高度遞增
var maxArea = 0
for (i in 0..heights.size) {
val h = if (i == heights.size) 0 else heights[i]
while (stack.isNotEmpty() && heights[stack.last()] >= h) {
val height = heights[stack.removeLast()]
val width = if (stack.isEmpty()) i else i - stack.last() - 1
maxArea = maxOf(maxArea, height * width)
}
stack.addLast(i)
}
return maxArea
}
}2. DP: Maintain height / left / right per cell — O(m·n) / O(n)
- Idea: 對每格算「高度、左邊界、右邊界」，矩形面積 =
(right - left) * height - Time:
O(m·n) - Space:
O(n)
class Solution {
fun maximalRectangle(matrix: Array<CharArray>): Int {
if (matrix.isEmpty()) return 0
val n = matrix[0].size
val height = IntArray(n)
val left = IntArray(n)
val right = IntArray(n) { n }
var maxArea = 0
for (row in matrix) {
for (j in 0 until n) height[j] = if (row[j] == '1') height[j] + 1 else 0
var curLeft = 0
for (j in 0 until n) {
if (row[j] == '1') left[j] = maxOf(left[j], curLeft) else { left[j] = 0; curLeft = j + 1 }
}
var curRight = n
for (j in n - 1 downTo 0) {
if (row[j] == '1') right[j] = minOf(right[j], curRight) else { right[j] = n; curRight = j }
}
for (j in 0 until n) maxArea = maxOf(maxArea, (right[j] - left[j]) * height[j])
}
return maxArea
}
}🔑 Takeaways
- Pattern: 降維——把二維矩形化為「逐列直方圖」，再套單調堆疊（84 的延伸）
- Key trick:
heights[j]累積連續 1 的高度是關鍵轉換；DP 解則靠 left/right 邊界陣列跨列遞推。先會 84 再看 85 會非常順