Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area = 10
unit.
For example,
Given heights = [2,1,5,6,2,3],
return 10.
一刷
题解：
思路一
保证stack内的元素都是升序。
遍历heights数组，如果大于栈顶元素，就push进去；否则，持续弹栈来计算从栈顶点到降序点的矩阵大小。为局部最大值
public class Solution {
public int largestRectangleArea(int[] height) {
int len = height.length;
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0;
for(int i = 0; i <= len; i++){
int h = (i == len ? 0 : height[i]);
if(s.isEmpty() || h >= height[s.peek()]){
s.push(i);
}else{
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}
}
注意⚠️：
思路：当前高度比peek小，则以peek高度为基准，不断pop直至stack中的元素都小与当前（保证站内元素递增）
- 在最后push了一个0，保证最后一个可以陆续pop出来计算面积。
- i--的用意是，不停pop直至stack中的元素都小与当前（重新进入for loop）
- 高度用
i - 1 - s.peek()的用意是，height[s.peek() + 1] >= height[tp]当前在栈顶的元素是tp左边的元素中第一个小于tp的。然而s.peek() + 1是大于tp的
ps:不在栈中的都比cur的高度要高
思路二
用栈来模拟，遍历heights数组，如果大于栈顶元素，就push进去；否则，持续弹栈来计算从栈顶点到降序点的矩阵大小。然后将这一部分全部替换为降序点的值，即做到了整体依然是有序非降的。
整个过程中，即把所有的局部最大矩阵计算过了，又在宽度范围内保留了全部的场景。
举例，2，1，5，6，3的场景。
1). 先加入一个0，方便最后可以全部弹栈出来。变成：2，1，5，6，3，0.
2). 2进栈，1比栈顶小，对2进行出栈，area = 2；
3). 2被替换为1进栈，1继续进栈，这是栈为1，1；
4). 5，6都是非降的，继续进栈，栈为1，1，5，6；
5). 遇到3，是一个降序点；开始弹栈，6出栈，对应area=61； 5出栈对应area=52；下一个1比3小，不需要弹栈。然后将5、6的弹栈后的空位压栈为3，这是栈为1，1，3，3，3；
6). 下一步遇到0，开始依次出栈，得到area=31，32，33，14，1*5。
7). 遍历结束。整个过程中max的area为10.
在整个过程中，将每一个点作为起点，到各个波峰最大的几个矩阵都计算过一次，即保证了每个点作为起点的最大矩阵可能性都试探过。
