T27205: 护林员盖房子又来了

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

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

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

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

样例输入

样例输出

提示

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

这是一个经典的算法问题，通常被称为“最大01矩阵”或“最大矩形面积”问题（Maximal Rectangle）。

解题思路

这个问题可以转化为：每一行都可以看作是一个直方图（Histogram）的底部，我们需要在这个直方图中找到最大的矩形面积。

降维处理：我们需要维护一个高度数组 heights，长度为列数 n。从第一行遍历到最后一行：
- 如果当前位置是 0（空地），说明高度可以累加，heights[j] += 1。
- 如果当前位置是 1（树木），说明断开了，高度重置为 0，heights[j] = 0。
计算直方图最大矩形：对于每一行更新后的 heights 数组，利用单调栈（Monotonic Stack）算法来计算当前直方图下的最大矩形面积。
- 单调栈维护的是高度递增的索引。
- 当遇到一个高度小于栈顶对应高度的柱子时，说明栈顶那个柱子向右无法延伸了，此时弹出栈顶，计算该柱子能构成的矩形面积。

复杂度分析

时间复杂度： $O (M \times N)$ 。我们需要遍历矩阵的每个元素一次，单调栈操作每个元素进栈出栈各一次。
空间复杂度： $O (N)$ 。主要用于存储高度数组和栈。

【李明阳25生科】提供图示。

Python 代码实现

python

import sys

def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        m = int(next(iterator))
        n = int(next(iterator))
    except StopIteration:
        return

    # heights 数组，用于记录当前行每一列向上连续的 '0' 的高度
    heights = [0] * n
    max_area = 0

    # 逐行处理
    for _ in range(m):
        # 读取当前行的 n 个数
        row_vals = []
        for _ in range(n):
            row_vals.append(int(next(iterator)))
        
        # 1. 更新高度 heights
        for j in range(n):
            if row_vals[j] == 0:
                # 如果是空地(0)，高度+1
                heights[j] += 1
            else:
                # 如果是树木(1)，高度归零
                heights[j] = 0
        
        # 2. 利用单调栈计算当前 heights 数组中的最大矩形面积
        # 在高度数组末尾添加一个 0，强迫栈中剩余元素在循环结束前全部弹出计算
        current_heights = heights + [0]
        stack = [-1] # 哨兵，方便计算宽度
        
        for i, h in enumerate(current_heights):
            # 当当前高度小于栈顶高度时，说明栈顶高度的矩形无法向右延伸了
            while stack[-1] != -1 and current_heights[stack[-1]] > h:
                height = current_heights[stack.pop()]
                width = i - stack[-1] - 1
                area = height * width
                if area > max_area:
                    max_area = area
            stack.append(i)

    print(max_area)

if __name__ == "__main__":
    # 设置递归深度以防万一，虽然本题主要是迭代
    sys.setrecursionlimit(2000)
    solve()

代码详解

输入处理：使用 sys.stdin.read().split() 一次性读取所有输入，这在大数据量（如 $1000 \times 1000$ ）时比 input() 更快。
维护 heights：
- 假设输入样例的第三行是 0 0 0 0 0，且上一行的高度结果是 [2, 0, 2, 1, 0]。
- 那么这一行更新后，heights 变为 [3, 1, 3, 2, 1]。
单调栈逻辑：
- 我们通过 current_heights = heights + [0] 添加一个高度为 0 的柱子在末尾。这保证了栈里所有累积的柱子最后都会被弹出来计算面积。
- 宽度计算公式 width = i - stack[-1] - 1：
  - i 是当前考察的柱子索引（右边界，不包含）。
  - stack[-1] 是弹出元素之后，栈里剩下的新栈顶（左边界，不包含）。
  - 两者之间的距离就是以“弹出元素的高度”为高的矩形的宽度。

样例验证

输入：

执行过程：

第1行 (0 1 0 1 1): heights -> [1, 0, 1, 0, 0]. 最大矩形面积 1。
第2行 (0 1 0 0 1): heights -> [2, 0, 2, 1, 0]. 最大矩形面积 2 (第一列的2 或者第三列的2)。
第3行 (0 0 0 0 0): heights -> [3, 1, 3, 2, 1].
- 单调栈计算中，当计算到高度1时，之前的3, 2等高度会被结算。
- 其中一个矩形由中间所有的1构成（跨度5，高度1），面积 = 5。
- 另一个矩形由左边的 [3, 1, 3] 中的 3 构成，面积3。
- 另一个由 [3, 2] 中的 2 构成，面积4。
- 当前最大面积更新为 5。
第4行 (0 1 1 0 1): heights -> [4, 0, 0, 3, 0]. 最大矩形面积 4 (第一列的4)。

最终输出：5。

与这个题目一样：T85.最大矩阵

monotonic stack, dp, https://leetcode.cn/problems/maximal-rectangle/description/

思路：化成直方图最大矩形问题的解法。

python

# ref: https://zhuanlan.zhihu.com/p/162834671

def maximalRectangle(matrix) -> int:
    # 求出行数n和列数m
    n = len(matrix)
    if n == 0:
        return 0

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

print(maximalRectangle(a))

T27205: 护林员盖房子又来了 ​

T27205: 护林员盖房子又来了