直方圖最大矩形面積問題（C 語言暴力解與優化思路）

問題描述

給定 N 個非負整數代表直方圖各柱高（寬度皆為 1），找出直方圖中面積最大的長方形面積。
例：heights = [2,1,5,6,2,3] → 最大面積 = 10（高 5、寬 2，對應索引 2、3）。

暴力解法 O(N³) → O(N²)

枚舉所有區間 [i, j]，面積 = (j-i+1) * min(heights[i..j])。
原始碼提供 minElement 掃描區間最小值，總複雜度 O(N³)。
稍加優化：外層固定 i，內層擴展 j 時同步維護最小值，降為 O(N²)。

原始碼（O(N²) 版）

int minElement(const int *h, int b, int e) {
    int min = h[b++];
    for (; b < e; ++b) if (h[b] < min) min = h[b];
    return min;
}

int largestRectangleArea(const int *height, int n) {
    int max = 0;
    for (int i = 0; i < n; ++i) {
        int min_h = height[i];
        for (int j = i; j < n; ++j) {
            if (height[j] < min_h) min_h = height[j];
            int area = (j - i + 1) * min_h;
            if (area > max) max = area;
        }
    }
    return max;
}

最佳解法：單調棧 O(N)

維護遞增棧存索引。遍歷每根柱，若當前高度 < 棧頂高度，彈出棧頂 tp，面積 = height[tp] * (棧空? i : i - stack[top-1] - 1)。最後清空棧計算剩餘面積。時間 O(N)、空間 O(N)。

單調棧參考實作

int largestRectangleArea_opt(const int *h, int n) {
    int *st = malloc(n * sizeof(int));
    int top = 0, max = 0;
    for (int i = 0; i <= n; ++i) {
        int cur = (i == n) ? 0 : h[i];
        while (top && cur < h[st[top-1]]) {
            int tp = st[--top];
            int width = top ? i - st[top-1] - 1 : i;
            int area = h[tp] * width;
            if (area > max) max = area;
        }
        st[top++] = i;
    }
    free(st);
    return max;
}

複雜度比較

測試範例

int main() {
    int h[] = {2,1,5,6,2,3};
    printf("暴力: %d\n", largestRectangleArea(h, 6)); // 10
    printf("單調棧: %d\n", largestRectangleArea_opt(h, 6)); // 10
    return 0;
}

圖解說明