LeetCode84. 柱状图中最大的矩形（2024冬季每日一题 16）

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

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

示例 1:

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

示例 2：

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

提示：

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

---

思路：单调栈

• 求最大面积 = hight * width
• 可以通过枚举 hight，也就是每个柱子，找到以此柱子为高度的矩形，随后我们从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，就确定了矩形的左右边界。如果左右边界之间的宽度为 $w$，那么对应的面积为 $w\times h$
• 此时，以 $h$ 为高度的矩形，就是左边边界中间的部分，此时 面积 = (right - left - 1) * h（不取左右边界）
• 而每个柱子对应的左右边界，可以通过单调栈求出来，即求出来离当前元素最近的，且严格小于当前元素的左/右边界元素下标
• 最后枚举每个柱子，计算其面积，求出来最大的面积返回即可

class Solution {
public:stack<int> lstk;stack<int> rstk;int l[100010], r[100010];int largestRectangleArea(vector<int>& h) {int n = h.size();l[0] = -1;lstk.push(0);for(int i = 1; i < n; i++){while(!lstk.empty() && h[lstk.top()] >= h[i]) lstk.pop();if(lstk.empty()) l[i] = -1;else l[i] = lstk.top();lstk.push(i);}r[n - 1] = n;rstk.push(n - 1);for(int i = n - 2; i >= 0; i--){while(!rstk.empty() && h[rstk.top()] >= h[i]) rstk.pop();if(rstk.empty()) r[i] = n;else r[i] = rstk.top();rstk.push(i);}int res = -1;for(int i = 0; i < n; i++){int ans = (r[i] - l[i] - 1) * h[i];res = max(res, ans);}return res;}
};