POJ 2559 Largest Rectangle in a Histogram：DP 預處理邊界 O(n) 解法

題目大意

同 HDU 1506：給定直方圖寬度為 1 的柱狀高度，求最大矩形面積。N ≤ 100000。

DP 邊界預處理

對每個 i，求左側第一個高度 < h[i] 的位置 L[i]，右側第一個高度 < h[i] 的位置 R[i]。

利用跳躍優化：

for (int i = 1; i <= n; i++) {
    L[i] = i;
    while (L[i] > 1 && h[i] <= h[L[i]-1])
        L[i] = L[L[i]-1];
}
for (int i = n-1; i >= 1; i--) {
    R[i] = i;
    while (R[i] < n && h[i] <= h[R[i]+1])
        R[i] = R[R[i]+1];
}

面積 = h[i] * (R[i] - L[i] + 1)，取最大值。

完整代碼

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100010;
int L[MAXN], R[MAXN], h[MAXN];

int main() {
    int n;
    while (cin >> n && n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &h[i]);
            L[i] = R[i] = i;
        }
        for (int i = 2; i <= n; ++i)
            while (L[i] > 1 && h[i] <= h[L[i]-1])
                L[i] = L[L[i]-1];
        for (int i = n-1; i >= 1; --i)
            while (R[i] < n && h[i] <= h[R[i]+1])
                R[i] = R[R[i]+1];
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, (long long)(R[i]-L[i]+1) * h[i]);
        cout << ans << endl;
    }
    return 0;
}

關鍵點

• 高度數組用 int，面積用 long long。
• 跳躍條件 h[i] <= h[L[i]-1] 保證嚴格遞增棧等價邏輯。
• 輸入多組，n=0 結束。

總結

POJ 2559 是直方圖最大矩形經典題，DP 跳躍預處理邊界 O(n) 代碼極短，是競賽常用模板。與 HDU 1506 同源，區別在於輸入格式與輸出格式細節。