HDU 1505 City Game：最大全 1 子矩陣的直方圖法 O(n²) 解法

問題描述

m×n 網格，每格 'F' (空地) 或 'R' (障礙)。找全 'F' 的最大面積矩形，輸出面積×3（每格 3 平方單位）。

核心轉化：逐行構建高度直方圖

對每一行 i，計算 height[j] = 以 (i,j) 為底向上連續 'F' 的格數。
則第 i 行問題轉化為：**直方圖中最大矩形面積** 經典問題。

單調棧 O(n) 求直方圖最大矩形

int largestRectangleArea(vector& h) {
    int n = h.size(), ans = 0;
    vector L(n), R(n), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
        L[i] = st.empty() ? 0 : st.back() + 1;
        st.push_back(i);
    }
    st.clear();
    for (int i = n-1; i >= 0; --i) {
        while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
        R[i] = st.empty() ? n-1 : st.back() - 1;
        st.push_back(i);
    }
    for (int i = 0; i < n; ++i)
        ans = max(ans, h[i] * (R[i] - L[i] + 1));
    return ans;
}

整體流程

int maxArea = 0;
vector h(n, 0);
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j)
        h[j] = (grid[i][j] == 'F') ? h[j] + 1 : 0;
    maxArea = max(maxArea, largestRectangleArea(h));
}
cout << maxArea * 3 << endl;

關鍵優化點

• 高度數組 h 逐行更新，空間 O(n)。
• 單調棧雙向掃描得左右邊界，總時間 O(mn)。
• 輸入用 scanf/getchar 加速，避免 cin 慢。

複雜度

時間 O(mn)，空間 O(n)。m,n ≤ 1000 時 10⁶ 操作，極快。