演算法經典：直方圖中最大矩形面積 - C 語言 O(n²) 暴力解與優化思路

題目描述

給定 n 個非負整數 height[0..n-1] 代表直方圖各柱高度，寬度皆為 1。找出能在直方圖內構成的最大矩形面積。例如 [2,1,5,6,2,3] 答案為 10（高度 5、寬度 2 的矩形）。

暴力解法：枚舉所有區間

時間複雜度 O(n³) → 優化為 O(n²)：固定左邊界，向右擴展並維護最小高度。

// 返回區間 [l, r] 最小值
static int min_in_range(const int *h, int l, int r) {
    int m = h[l];
    for (int i = l+1; i <= r; ++i)
        if (h[i] < m) m = h[i];
    return m;
}

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

• 內層迴圈維護 minH 避免重複掃描，將 O(n³) 降為 O(n²)。
• 適合 n ≤ 5000 的資料範圍。

最優解：單調棧 O(n)

核心觀察：對每根柱子，找到其左側第一根更矮的柱子（左邊界）與右側第一根更矮的柱子（右邊界），該柱子能構成的最大矩形寬度即 right - left - 1。

int largestRectangleArea_stack(const int *height, int n) {
    int *st = malloc(n * sizeof(int));
    int top = -1;
    int maxArea = 0;

    for (int i = 0; i <= n; ++i) {
        int curH = (i == n) ? 0 : height[i]; // 哨兵 0 強制彈出所有
        while (top >= 0 && curH < height[st[top]]) {
            int h = height[st[top--]];
            int left = (top >= 0) ? st[top] : -1;
            int width = i - left - 1;
            int area = h * width;
            if (area > maxArea) maxArea = area;
        }
        st[++top] = i;
    }
    free(st);
    return maxArea;
}

• 棧存遞增高度的索引。
• 遇到更矮柱子，彈出棧頂計算該高度能延伸的最大寬度。
• 最後補一個高度 0 的哨兵，確保棧清空。
• 時間 O(n)，空間 O(n)。

分治法 O(n log n) 平均

找全局最小高度分割左右遞迴，類似 QuickSort，最壞 O(n²)（已排序陣列）。

測試驗證

int main() {
    int h1[] = {2,1,5,6,2,3};
    int h2[] = {2,4};
    int h3[] = {5,4,3,2,1};
    printf("%d\n", largestRectangleArea_stack(h1, 6)); // 10
    printf("%d\n", largestRectangleArea_stack(h2, 2)); // 4
    printf("%d\n", largestRectangleArea_stack(h3, 5)); // 9
    return 0;
}

工程選型建議

總結

直方圖最大矩形是棿應用的經典案例。從 O(n³) 到 O(n²) 再到 O(n)，每一步優化都對應一個核心觀察：避免重複計算最小值 → 利用單調性一次遍歷確定邊界。掌握單調棧模板，可舉一反三解決「接雨水」、「最大子矩陣」、「股票跨度」等同構問題。