最大矩形

Leetcode Link: 85. 最大矩形 - 力扣（LeetCode）

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

解法一

思路：

思路同柱状图中最大的矩形，与之相比，这个相对更复杂一点，大体思路为

1. 遍历 matrix 的每一行
2. 计算当前行的 height，注意从根部算起，悬空的不算。（height 意义和柱状图中最大的矩形一样）
3. 按照柱状图中最大的矩形的思路计算当前 height 下的最大面积
4. 重复 23

本题解仿照了柱状图中最大的矩形中给出的题解链接的形式来写代码，栈中不在保存高度，而只保存位置 i，使用-1 作为哨兵，避免空栈的判断。 但是这样需要额外判断当前栈顶的是不是-1，不然如果看栈顶的高度时恰好栈顶是-1，则会执行bar[stack[-1][0]]=bar[-1]。坑的是这不会报错，而是会比较bar的最后一个元素的高，这是错误的。

题解：

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        res = -float('inf')
        for row in range(len(matrix)):
            bar = self.get_bar(matrix, row)
            stack = [[-1]]
            for idx, h in enumerate(bar):
                while(len(stack) > 1 and h < bar[stack[-1][0]]):
                    cur = stack.pop()
                    for x in cur:
                        res = max(bar[x]*(idx-stack[-1][-1]-1), res)
                # 注意这里务必需要先判定栈顶是不是-1
                if stack[-1][0] == -1 or h > bar[stack[-1][0]]:
                    stack.append([idx])
                else:
                    stack[-1].append(idx)
            
            while(len(stack) > 1):
                cur = stack.pop()
                for x in cur:
                    res = max(res, bar[x]*(len(bar)-stack[-1][-1]-1))
        
        return res
        
	# 获取当前行的bar，即84题的height
    def get_bar(self, matrix, row):
        bar = [0]*len(matrix[0])
        for j in range(len(matrix[0])):
            tmp = 0
            i = row
            while(matrix[i][j]== '1' and i >=0):
                tmp += 1
                i -= 1
            bar[j] = tmp
        return bar

解法二

思路： #算法/动态规划 来做。

题解：

解法三

思路：

题解：

启发和联系

同类题接雨水