Largest Rectangle In Histogram

84. 柱状图中的最大矩形

分析

确定左右边界：
- 左边界：对于柱子 heights[i]，寻找它左边第一个比它小的柱子位置 left[i]
  - 使用一个单调递增栈，从左到右遍历数组：
    - 当前柱子比栈顶柱子低时，弹出栈顶柱子，找到当前柱子作为某柱右边界的场景
    - 当前柱子的左边界就是栈顶元素（若栈为空，则左边界为 -1）
- 右边界：对于柱子 heights[i]，寻找它右边第一个比它小的柱子位置 right[i]
  - 使用相同逻辑，从右向左遍历数组，确定每个柱子的右边界
- 利用单调栈快速找到这些边界
计算最大矩形面积：
- 每个柱子的宽度 = right[i] - left[i] - 1
- 面积 = 柱高度 × 宽度，取最大值

时间复杂度

每个柱子在左右边界的遍历中最多进栈和出栈一次，总时间复杂度为 O(n)

空间复杂度

需要存储左右边界和栈，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution
{
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int n = heights.size();
        std::vector<int> left(n), right(n); // 左边界和右边界
        std::stack<int> stk;

        // 确定左边界
        for (int i = 0; i < n; ++i)
        {
            while (!stk.empty() && heights[i] <= heights[stk.top()])
                stk.pop();
            left[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }

        // 清空栈，重新计算右边界
        stk = std::stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!stk.empty() && heights[i] <= heights[stk.top()])
                stk.pop();
            right[i] = stk.empty() ? n : stk.top();
            stk.push(i);
        }

        // 计算最大矩形面积
        int res = 0;
        for (int i = 0; i < n; ++i)
            res = std::max(res, heights[i] * (right[i] - left[i] - 1));

        return res;
    }
};