T27205: 护林员盖房子加强版

monotonous stack, http://cs101.openjudge.cn/practice/27205

在一片保护林中，护林员想要盖一座房子来居住，但他不能砍伐任何树木。现在请你帮他计算：保护林中所能用来盖房子的矩形空地的最大面积。

输入保护林用一个二维矩阵来表示，长宽都不超过20（即<=20）。第一行是两个正整数m,n，表示矩阵有m行n列。然后是m行，每行n个整数，用1代表树木，用0表示空地。

输出一个正整数，表示保护林中能用来盖房子的最大矩形空地面积。

样例输入

样例输出

提示

子矩阵边长可以为1，也就是说： 0 0 0 0 0 依然是一个可以盖房子的子矩阵。

看成是以不同的底竖直摆放的矩形的高度。

LeetCode 85 | 如何从矩阵当中找到数字围成的最大矩形的面积？https://zhuanlan.zhihu.com/p/162834671

python

def maximalRectangle(matrix) -> int:
    if (rows := len(matrix)) == 0:
        return 0

    cols = len(matrix[0])
    # 存储每一层的高度
    height = [0 for _ in range(cols + 1)]
    res = 0

    for i in range(rows):  # 遍历以哪一层作为底层
        stack = [-1]
        for j in range(cols + 1):
            # 计算j位置的高度，如果遇到1则置为0，否则递增
            h = 0 if j == cols or matrix[i][j] == '1' else height[j] + 1
            height[j] = h
            # 单调栈维护长度
            while len(stack) > 1 and h < height[stack[-1]]:
                res = max(res, (j - stack[-2] - 1) * height[stack[-1]])
                stack.pop()
            stack.append(j)
    return res


rows, _ = map(int, input().split())
a = [input().split() for _ in range(rows)]

print(maximalRectangle(a))

T27205: 护林员盖房子 加强版 ​

T27205: 护林员盖房子加强版