Given an array of integers heights
representing the histogram's bar height where the width of each bar is 1
, return the area of the largest rectangle in the histogram.
Example 1:
![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
逐个将元素 push 到栈里。push 进去之前先把 > 自己的元素 pop 出来。 每次从栈中 pop 出一个数的时候,就找到了往左数比它小的第一个数(当前栈顶)和往右数比它小的第一个数(即将入栈的数), 从而可以计算出这两个数中间的部分宽度 * 被pop出的数,就是以这个被pop出来的数为最低的那个直方向两边展开的最大矩阵面积。 因为要计算两个数中间的宽度,因此放在 stack 里的是每个数的下标
public static int largestRectangleArea(int[] height) {标签:return,int,max,pop,height,Rectangle,Histogram,stack,84 From: https://www.cnblogs.com/MarkLeeBYR/p/16892231.html
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>(); //维护单调递增
int max = 0;
for (int i = 0; i <= height.length; i++) {
int curt = (i == height.length) ? -1 : height[i];
while (!stack.isEmpty() && curt <= height[stack.peek()]) { //如果栈顶高度大于当前高度
int h = height[stack.pop()]; //保存栈顶元素信息
int w = stack.isEmpty() ? i : i - stack.peek() - 1; //如果栈已经为空,宽度为i,否则i-s.top()-1
max = Math.max(max, h * w);
}
stack.push(i); //压入栈中
}
return max;
}