题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
单调栈，left和right分别存储的是当前i左边第一个高度小于i高度的位置，当前i右边第一个高度小于等于i高度的位置。
当遍历完数组时stack里还有元素，则stack中的元素的right都是n。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right,n);
Stack<Integer> stack = new Stack<>();
for(int i = 0;i < n;i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
right[stack.peek()] = i;
stack.pop();
}
left[i] = stack.isEmpty()?-1:stack.peek();
stack.push(i);
}
int res = 0;
for(int i = 0;i < n;i++){
res = Math.max(res,(right[i]-left[i]-1)*heights[i]);
}
return res;
}
}
本文地址：https://blog.csdn.net/weixin_42529866/article/details/110207814
![2022-01-21：完美矩形。 给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi,](https://www.kunjuke.com/file/css/thumb/3.jpg/280-180.jpg)
![2022-10-09：我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
