85 Maximum Rectangle

https://leetcode.com/problems/maximal-rectangle/

solution

• 单调栈: 按行迭代，每一行都视为柱状图的底部，对每一行求柱状图的最大面积

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()

follow up

84 Largest Rectangle in Histogram

221 Maximal Square