HDU 1505 City Game：最大子矩陣面積的直方圖法推廣

題目描述

給定 m×n 的 0/1 矩陣（'F' 視為 1，'R' 視為 0），求全 1 子矩陣的最大面積，輸出面積×3。多測試案例。m,n ≤ 1000。

核心思路：逐行構建直方圖 + 單調棧

將二維問題轉化為一維「最大矩形面積」問題（POJ 1506 / HDU 1506）：

1. 掃描每一行，維護 height[j] = 該列連續 1 的高度（若當前格為 0 則歸 0）。
2. 對每行的 height[1..n]，求直方圖中最大矩形面積。
   經典 O(n) 單調棧做法：
   - L[j]：左側第一個高度 < height[j] 的位置。
   - R[j]：右側第一個高度 < height[j] 的位置。
   - 以 j 為最低高度的最大矩形寬度 = R[j] - L[j] - 1，面積 = height[j] * 寬度。
3. 全局最大面積乘 3 輸出。

關鍵代碼片段

int height[1005], L[1005], R[1005];
char s[10];

for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        scanf("%s", s);
        if (s[0] == 'F') height[j] += 1;
        else height[j] = 0;
    }
    // 求 L[]
    for (int j = 1; j <= n; ++j) {
        L[j] = j;
        while (L[j] > 1 && height[L[j]-1] >= height[j])
            L[j] = L[L[j]-1]; // 跳躍優化
    }
    // 求 R[]
    for (int j = n; j >= 1; --j) {
        R[j] = j;
        while (R[j] < n && height[R[j]+1] >= height[j])
            R[j] = R[R[j]+1];
    }
    for (int j = 1; j <= n; ++j)
        ans = max(ans, height[j] * (R[j] - L[j] + 1));
}
printf("%d\n", 3 * ans);

複雜度分析

• 時間：O(m × n) = 10⁶，單調棧摊還 O(1) 每列。
• 空間：O(n) = 1000。

易錯點提醒

• 輸入字符 'F'/'R' 需用 %s 讀取字符串，取 s[0] 判斷。
• height、L、R 數組大小開 n+2 避免越界。
• 跳躍優化 L[j] = L[L[j]-1] 是將 O(n²) 降為 O(n) 的關鍵。
• 最終答案乘 3，別忘了。

總結

HDU 1505 是「最大全 1 子矩陣」的標準解法：逐行構建直方圖高度，配合單調棧 O(n) 求最大矩形。掌握此模板，可解決所有二維 0/1 矩陣最大子矩陣問題。