HDU 1506 Largest Rectangle in a Histogram：單調棧 / DP 求最大矩形面積

題目大意

給定 n 個寬度為 1 的相鄰矩形，高度為 h[i]。求能在直方圖內形成的最大矩形面積。n ≤ 100000，高度 ≤ 2^31-1，需 64 位整數。

方法一：DP 預處理左右邊界（O(n)）

對每個 i，求左側第一個高度 < h[i] 的位置 L[i]，右側第一個高度 < h[i] 的位置 R[i]。則以 h[i] 為高的最大矩形寬度 = R[i] - L[i] - 1。

利用 DP 跳躍優化：

for (int i = 1; i <= n; i++) {
    L[i] = i;
    while (L[i] > 1 && h[L[i]-1] >= h[i])
        L[i] = L[L[i]-1]; // 跳躍到更遠的邊界
}
for (int i = n; i >= 1; i--) {
    R[i] = i;
    while (R[i] < n && h[R[i]+1] >= h[i])
        R[i] = R[R[i]+1];
}

這裡利用已計算好的 L/R 跳過中間已知不比 h[i] 矮的位置，實現攤還 O(1) 邊界查找。

方法二：單調棧（O(n)）

維護遞增棧存下標。遍歷 i=1..n：

• 若棧空或 h[i] ≥ h[棧頂]，入棧。
• 否則反覆彈出棧頂 top，以 h[top] 為高，左邊界為新棧頂，右邊界為 i-1，計算面積更新答案，直到可入棧。

遍歷結束後將棧中剩餘元素彈出計算（右邊界 = n）。

代碼實現（DP 版）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
LL h[MAXN];
int L[MAXN], R[MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
        for (int i = 1; i <= n; i++) {
            L[i] = i;
            while (L[i] > 1 && h[L[i]-1] >= h[i])
                L[i] = L[L[i]-1];
        }
        for (int i = n; i >= 1; i--) {
            R[i] = i;
            while (R[i] < n && h[R[i]+1] >= h[i])
                R[i] = R[R[i]+1];
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            LL area = h[i] * (R[i] - L[i] + 1);
            if (area > ans) ans = area;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點總結

• 高度數組必須用 long long，面積可能超過 32 位。
• DP 邊界跳躍技巧：L[i] = L[L[i]-1] 利用已計算結果實現 O(n)。
• 單調棧代碼更簡短，但 DP 版思路更直觀易記。
• 輸入多組測試案例，以 n=0 結束。

總結

直方圖最大矩形是經典問題，DP 預處理邊界與單調棧均為 O(n) 最優解。本題數據範圍要求 64 位整數，注意類型定義。DP 版跳躍優化代碼簡潔高效，是競賽常用模板。