给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3] 输出: 10
思路：找出当前高度的最大宽度（关键是确定左边界和右边界）
左/右边界：左/右第一个小于当前高度对应的索引
通过维护一个单调栈（递增），得到当前栈顶对应索引的高度的左右边界，更新最大面积。
class Solution { public int largestRectangleArea(int[] heights) { // 单调栈 if(heights.length==0) return 0; // 数组heights末尾添加一个0元素，保证右边界可达 int[] heights2=new int[heights.length+1]; for(int i=0;i<heights.length;i++) heights2[i]=heights[i]; // 栈用来保存数组中值的索引，并维护单调性 Stack<Integer> stack=new Stack<>(); int maxArea=0; // 维护一个单调递增栈 for(int i=0;i<heights2.length;i++){ while(!stack.empty() && heights2[i]<heights2[stack.peek()]){ // 以当前栈顶下标对应的值为height int top=stack.peek(); stack.pop(); maxArea=Math.max(maxArea,heights2[top]*(stack.empty()?i:i-stack.peek()-1)); } stack.push(i); } return maxArea; } }
