📝 题目描述

题目链接：柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例：

示例 1：

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

1
2
输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

💡 解题思路

方法一：单调栈

这个题跟接雨水比较相像，接雨水要找出一个柱子左右两边第一个大于该柱子高度的柱子，本题是找每个柱子左右两边第一个小于该柱子的柱子。

本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序。

为了不再判断特例，可以设置两个哨兵节点，也就是高度为 0 的柱子到题目数组的两边，以便于我们及时将所有元素出栈。

维护一个非严格单调递增栈：

  • 栈非空且当前遍历到的元素 heights[i] 比栈顶元素 heights[stk.top()] 小，那么说明我们的栈顶元素可以出栈了。
    • 对于栈顶元素 stk.top() 我们可以想象，首先可以确定当前元素 i 比其要低，那么我们无法继续向遍历方向拓展，又可得知我们是一个非严格单调递增栈，唯一向遍历方向相反的方向拓展的可能是紧挨着自己有相同高度的柱子。于是我们可以计算出高度 height = heights[stk.top()]；宽度我们可以设置一个循环，如果新栈顶元素高度与自己相同，则可以继续出栈，否则计算宽度 width = stk.top() - i - 1，计算出面积并更新最大值。
  • 重复上面的流程，然后将当前遍历到的元素 i 入栈。

🔧 代码实现

1、单调栈

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int area = 0;
        // 设置哨兵节点，不用特判
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        // 维护一个非严格单调递增栈
        stack<int> stk;
        // 倒序遍历，按照模板写法
        for(int i = heights.size() - 1; i >= 0; i--) {
            // 当前高度小于栈顶高度，则栈顶元素可以出栈
            while(!stk.empty() && heights[i] < heights[stk.top()]) {
                // 获取栈顶元素高度
                int height = heights[stk.top()];
                // 为了严谨，同高度的柱子可以连续出栈
                while(!stk.empty() && heights[stk.top()] == height) {
                    stk.pop();
                }
                // 计算宽度
                int width = stk.top() - i - 1;
                // 更新最大值
                area = max(area, height * width);
            }
            stk.push(i);
        }
        return area;
    }
};

📊 复杂度分析

1、单调栈

  • 时间复杂度：O(N)O(N)，每个元素最多入栈一次、出栈一次。
  • 空间复杂度：O(N)O(N)，使用一个栈和若干常数变量。

🎯 总结

  • 核心思想：掌握单调栈的模板写法。