https://leetcode.com/problems/maximal-rectangle/
- 单调栈: 按行迭代，每一行都视为柱状图的底部，对每一行求柱状图的最大面积
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
n = len(matrix[0])
heights = [0] * (n + 1)
max_area = 0
for row in matrix:
# 构建如84题的高度
for i in range(n):
heights[i] = heights[i] + 1 if row[i] == "1" else 0
stack = [-1]
for i in range(n + 1):
# 单调栈: 右边第一个高度比自己小的index构成矩形
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1 # 左右两边第一个比自己小
max_area = max(max_area, h * w)
stack.append(i)
return max_area时间复杂度：O(mn)
空间复杂度：O(n)
- 动态规划: 一开始想到的dp没法处理前面一个单元是正方形，后面连着的只是单个
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
ans = 0
dp = {}
for i in range(m):
for j in range(n):
if matrix[i][j] == '0':
dp[(i,j)] = (0,0)
else:
x = dp[(i, j-1)][0]+1 if j>0 else 1
y = dp[(i-1, j)][1]+1 if i>0 else 1
dp[(i, j)] = (x, y)
ans = max(x, y, ans)
minWidth = x
# vertical max possible
for r in range(i-1, i-y, -1):
minWidth = min(minWidth, dp[(r, j)][0])
ans = max(ans, minWidth * (i-r+1))
return ans时间复杂度：O()
空间复杂度：O()