玉蟾宫

GitHub跳转原题关系图返回列表

逐行把连续 F 高度压成直方图，并用单调栈求每行结尾的最大矩形面积。

OJ: luogu

题目 ID: P4147

难度:普及+/提高

标签:单调栈矩阵python

日期: 2026-07-16 18:25

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

在 F/R 网格中找全为 F 的最大矩形，输出面积的三倍。

思路

逐行维护 heights[j]：当前位置为 F 就加一，否则清零。每一行都得到一个直方图，所有以下边界在当前行的合法矩形都对应直方图中的矩形。

用递增高度栈处理直方图；遇到更矮柱子时弹出旧高度，并以当前列为右边界结算面积。末尾追加高度 0 的逻辑清空栈。

Python 知识

  • enumerate(input().split()) 直接更新每列高度。
  • 栈元素 (start, height) 同时记录该高度最早能向左延伸的位置。
  • 普通列表尾部操作足够实现单调栈。

代码

python
import sys


input = sys.stdin.buffer.readline
rows, columns = map(int, input().split())
heights = [0] * columns
best = 0

for _ in range(rows):
    for j, cell in enumerate(input().split()):
        heights[j] = heights[j] + 1 if cell == b"F" else 0

    stack = []
    for j in range(columns + 1):
        height = heights[j] if j < columns else 0
        start = j
        while stack and stack[-1][1] > height:
            start, previous_height = stack.pop()
            best = max(best, previous_height * (j - start))
        if not stack or stack[-1][1] < height:
            stack.append((start, height))

print(3 * best)

复杂度

时间复杂度 O(NM)O(NM)，空间复杂度 O(M)O(M)。

总结

二维全 1 最大矩形可以逐行转成经典直方图最大矩形。