題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P4147 玉蟾宫

Problem Statement

題目簡述

給定一個 N×MN \times M 的矩陣，矩陣中的元素為 'F' 或 'R'。
求出一個完全由 'F' 組成的最大矩形，並輸出該矩形面積乘以 33 的結果。

Constraints

約束條件

  • 1≤N,M≤10001 \le N, M \le 1000

思路：單調棧

這道題與 85. Maximal Rectangle 完全相同。
我們可以將二維矩陣的問題轉化為一維的「直方圖中最大矩形」問題，即 84. Largest Rectangle in Histogram。

降維轉換

我們可以逐行遍歷矩陣，並維護每一列連續 'F' 的高度。
對於每一行，我們將其視為直方圖的底邊，此時每一列的高度就構成了直方圖的各個柱子。
問題就轉化為：在當前直方圖中，找到一個面積最大的矩形。

單調棧求解

為了解決直方圖中最大矩形的問題，我們可以使用單調棧。
單調棧可以用來快速找到每個柱子左邊和右邊第一個比它矮的柱子位置。
這樣，我們就能知道以當前柱子高度為高時，矩形可以向左右延伸的最大寬度。

核心概念

對於任意一個柱子，如果我們想以它的高度作為矩形的高度，那麼這個矩形向左和向右延伸的極限，必定是遇到第一個比它矮的柱子。

在實作上，我們可以在遍歷柱子時維護一個嚴格遞增的單調棧：

  1. 當遇到一個比棧頂柱子矮的柱子時，說明棧頂柱子的右邊界已經確定。
  2. 此時彈出棧頂柱子，其左邊界就是彈出後新的棧頂柱子位置。
  3. 利用左右邊界，我們就可以計算出以該柱子為高的最大矩形面積，並更新全局最大值。
邊界處理

為了確保所有柱子都能被正確計算（特別是遞增到最後的柱子），我們可以在高度陣列的頭尾各加上一個高度為 00 的虛擬柱子。這樣可以保證所有真實的柱子最終都會因為遇到右側的 00 而出棧並計算面積。

複雜度分析

  • 時間複雜度：O(N×M)\mathcal{O}(N \times M)，其中 NN 和 MM 分別為矩陣的行數和列數。每個元素最多入棧和出棧一次。
  • 空間複雜度：O(M)\mathcal{O}(M)，需要一個陣列來儲存每一列的高度，以及一個單調棧，兩者的大小都不超過 M+2M+2。
參考資料

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solve():
    n, m = map(int, input().split())
    matrix = [input().split() for _ in range(n)]

    ans = 0
    heights = [0] * (m + 2)
    for row in matrix:
        for i, ch in enumerate(row, start=1):
            heights[i] = heights[i] + 1 if ch == "F" else 0
        # 84. Largest Rectangle in Histogram
        st = []
        for right, x in enumerate(heights):
            while st and x < heights[st[-1]]:
                idx = st.pop()  # idx 為當前的柱子
                if st:
                    # right 為右邊比當前矮的位置，left = st[-1] 為左邊比當前矮的位置
                    left = st[-1]
                    # 高度為 heights[idx] 的柱子可以向左右延伸的最大寬度為 right - left - 1
                    ans = max(ans, heights[idx] * (right - left - 1))
            st.append(right)
    print(ans * 3)


if __name__ == "__main__":
    solve()