玉蟾宫

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

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

OJ: luogu

题目 ID: P4147

难度:普及+/提高-

标签:单调栈矩阵python

创建: 2026-07-16 18:25

更新: 2026-10-07 12:15

前置题目
luogu P3467[POI 2008] PLA-PosteringB 的直方图最大矩形复用 A 教的「递增高度栈、遇更矮就弹出已结束高度层」这一步（只是弹出时改以当前列为右边界结算面积），再叠加逐行 heights 清零建直方图与高度 0 哨兵清栈。shumeng CSP201312C最大的矩形B 把 A 教的直方图最大矩形单调栈原语（弹栈新栈顶为左界、当前为右界、0 哨兵清空栈）逐行套用，额外只做 heights 二维转一维roj 3032「Largest Rectangle in a Histogram」 直方图中最大的矩形B 把 A 教的单调栈弹出结算（新栈顶为左界、当前列为右界、末尾补 0 哨兵）作为内层原语，逐行维护 heights 压成直方图后再套用一次，额外流程只是二维转一维。

目录

  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 最大矩形可以逐行转成经典直方图最大矩形。