问题背景

给定 $n$ 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 $1$。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

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

数据约束

• $1\le heights.length\le 10^5$
• $0\le heights[i]\le 10^4$

解题过程

单调栈应用题，参照 模板 能顺利解决。
从这里可以总结出来，单调栈的作用就是针对数组中的每个元素，求出对它而言符合某个条件的前后缀。
在本题中，确定了最大面积的高度一定是数组中元素的情况下，要求的就是对每个元素而言宽度的最大值。进一步就转化为了找到对于每个位置上的元素，离它最近最近的小于它的元素。
注意求宽度的时候要根据具体情况修正数值，找特殊值验证就可以了。

具体实现

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] left = new int[n];Deque<Integer> stack = new ArrayDeque<>();for(int i = 0; i < n; i++) {int cur = heights[i];while(!stack.isEmpty() && cur <= heights[stack.peek()]) {stack.pop();}left[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(i);}int[] right = new int[n];stack.clear();for(int i = n - 1; i >= 0; i--) {int cur = heights[i];while(!stack.isEmpty() && cur <= heights[stack.peek()]) {stack.pop();}right[i] = stack.isEmpty() ? n : stack.peek();stack.push(i);}int res = 0;for(int i = 0; i < n; i++) {res = Math.max(res, heights[i] * (right[i] - left[i] - 1));}return res;}
}