LeetCode84 柱状图中的最大矩形
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=105
0 <= heights[i] <= 104
方法
单调栈法
遍历数组，分别找到左边和右边第一个小于当前下标的值，然后用左右的值为边界与当前高度计算面积
注意：left的默认值为-1，right的默认值为length;
- 时间复杂度：O（n）
- 空间复杂度：O（n）
class Solution {
public int largestRectangleArea(int[] heights) {
int length = heights.length;
Stack stack = new Stack<>();
int[] left = new int[length];
int[] right = new int[length];
for(int i=0;i=0;i--){
while(!stack.isEmpty()&&heights[i]<=heights[stack.peek()]){
stack.pop();
}
right[i] = stack.isEmpty()?length:stack.peek();
stack.push(i);
}
int max = 0;
for(int i=0;i 单调栈优化法
单调栈法是分别找到左边和右边的第一个小于值，在获取left数组时，当有出栈操作时，说明heights[i]<=heights[stack.peek()]，这样可以得出stack.peek()的右侧最小值边界为i，因此只要有出栈操作就能更新stack.peek()的right数组，如果没有出栈则说明右侧没有比他更小的则为length;
- 时间复杂度：O（n）
- 空间复杂度：O（n）
class Solution {
public int largestRectangleArea(int[] heights) {
int length = heights.length;
Stack stack = new Stack<>();
int[] left = new int[length];
int[] right = new int[length];
Arrays.fill(right,length);
for(int i=0;i