84. 柱状图中最大的矩形

📝 题目描述

给定 n 个非负整数，代表柱状图中每个柱子的高度（每个柱子宽度为1，彼此相邻）。求该柱状图中能够勾勒出的矩形的最大面积。

---

📌 示例

示例 1

输入：

heights = [2,1,5,6,2,3]

输出：

10

解释：以高度为5的柱子为核心，可向左右扩展到宽度2（左边界是下标1，右边界是下标4），面积为 (5 \times 2 = 10)（对应图中红色区域）。

---

🚀 最优解：单调栈法（找左右边界）

🔍 思路解析

核心策略：对每个柱子，找到它作为“矩形高度”时能扩展的左右边界（左边第一个比它矮的柱子、右边第一个比它矮的柱子），计算该柱子对应的最大面积，最终取所有面积的最大值。

单调栈的作用是高效维护递增的柱子序列，从而快速确定每个柱子的左右边界：

1. 预处理数组：在原数组前后各加一个“哨兵”（高度为0），避免处理栈空或遍历结束后剩余元素的情况；
2. 初始化单调栈：栈中存储柱子的下标，保持栈内下标的对应高度递增；
3. 遍历预处理后的数组：
   • 若当前柱子高度 < 栈顶下标对应的高度：
     • 弹出栈顶下标，将其对应的高度作为当前计算的矩形高度；
     • 新的栈顶下标是“左边界”（第一个比当前高度矮的柱子）；
     • 当前遍历的下标是“右边界”（第一个比当前高度矮的柱子）；
     • 计算面积：(高度 \times (右边界 - 左边界 - 1))，更新最大面积；
   • 将当前下标入栈。

---

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read heights array
        String input = scanner.nextLine();
        input = input.substring(1, input.length() - 1); // Remove brackets
        String[] heightsStr = input.split(",");

        int[] heights = new int[heightsStr.length];
        for (int i = 0; i < heightsStr.length; i++) {
            heights[i] = Integer.parseInt(heightsStr[i].trim());
        }

        Solution solution = new Solution();
        int result = solution.largestRectangleArea(heights);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 预处理：前后加哨兵（高度0），避免边界处理
        int[] newHeights = new int[n + 2];
        System.arraycopy(heights, 0, newHeights, 1, n);

        Deque<Integer> stack = new LinkedList<>();
        int maxArea = 0;

        for (int i = 0; i < newHeights.length; i++) {
            // 当前高度 < 栈顶高度，计算栈顶对应的面积
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                int h = newHeights[stack.pop()]; // 当前计算的高度
                int left = stack.peek();         // 左边界（栈顶是第一个比h矮的）
                int width = i - left - 1;        // 宽度：右边界-左边界-1
                maxArea = Math.max(maxArea, h * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

---

🧠 通俗易懂解释

可以把每个柱子想象成“能撑多大的矩形”：

• 每个柱子的“撑的范围”由左右第一个比它矮的柱子决定（矮柱子会挡住它的扩展）；
• 单调栈就像“排队的柱子”，只留“越来越高”的柱子，一旦遇到更矮的柱子，就可以确定前面高柱子的“撑的范围”，计算面积后让高柱子“退场”。

以示例 heights = [2,1,5,6,2,3] 为例（预处理后是 [0,2,1,5,6,2,3,0]）：

1. 遍历到下标2（高度1）：比栈顶下标1（高度2）矮，弹出下标1，左边界是下标0（哨兵），宽度=2-0-1=1，面积=2×1=2；
2. 遍历到下标5（高度2）：比栈顶下标4（高度6）矮，弹出下标4，左边界是下标3（高度5），宽度=5-3-1=1，面积=6×1=6；
3. 继续：当前高度2仍比栈顶下标3（高度5）矮，弹出下标3，左边界是下标2（高度1），宽度=5-2-1=2，面积=5×2=10（更新最大面积）；
4. 后续遍历会计算其他柱子的面积，但最大面积已为10。

---

⏱ 时间复杂度

(O(n))

每个柱子仅入栈、出栈各一次，遍历预处理数组的时间为线性级。

---

💾 空间复杂度

(O(n))

预处理数组的空间为 (O(n))，单调栈的空间最多为 (O(n))（最坏情况所有柱子递增）。