柱状图中最大的矩形

核心是用单调递增栈快速定位每个柱子的左右边界，计算以该柱子为高的最大矩形面积，然后取所有最大矩形最大值 以下是代码解析：

  class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        // 首尾加0，简化边界处理
        vector<int> res(heights.size() + 2, 0);
        for (int i = 0; i < heights.size(); ++i) {
            res[i + 1] = heights[i];
        }
        stack<int> stk; // 单调递增栈，存储res的下标
        int maxArea = 0;
        for (int i = 0; i < res.size(); ++i) {
            // 当前元素更小，触发栈顶元素的面积计算
            while (!stk.empty() && res[i] < res[stk.top()]) {
                int h = res[stk.top()]; // 取栈顶元素的高度
                stk.pop();
                int w = i - stk.top() - 1; // 计算矩形宽度
                maxArea = max(maxArea, h * w); // 更新最大面积
            }
            stk.push(i); // 下标入栈，维持栈递增
        }
        return maxArea;
    }
};
该解法的时间复杂度为O(n)，空间复杂度为O(n)