给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

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

 1 class Solution {
 2     public int largestRectangleArea(int[] heights) {
 3         int length = heights.length;
 4         int []left = new int[length];
 5         int []right = new int[length];
 6         // 利用单调栈，从左往右遍历，找到比自己小的下标
 7         Deque<Integer> leftStack = new ArrayDeque<>();
 8         for (int i=0;i<length;i++){
 9             while (!leftStack.isEmpty() && heights[leftStack.peek()]>=heights[i]){
10                 // 比栈内的小，则将栈内元素弹出
11                 leftStack.pop();
12             }
13             // 更新左边比自己小的元素位置
14             left[i]=leftStack.isEmpty()?-1:leftStack.peek();
15             // 将本身的位置塞入
16             leftStack.push(i);
17         }
18         // 从右往左遍历，找到比自己小的下标
19         Deque<Integer> rightStack = new ArrayDeque<>();
20         for (int i = length-1;i>=0;i--){
21             while (!rightStack.isEmpty() && heights[rightStack.peek()] >= heights[i]){
22                 rightStack.pop();
23             }
24             right[i] = rightStack.isEmpty()?length:rightStack.peek();
25             rightStack.push(i);
26         }
27         // 循环，计算每个位置往左右延伸可以达到的最大的面积
28         int maxLength = 0;
29         for (int i =0 ;i<length;i++){
30             maxLength = Math.max(maxLength,heights[i]*(right[i]-left[i]-1));
31         }
32         return maxLength;
33     }
34 }

解题关键：

1.单调栈。

2.分别从左和从右遍历，记录左右两边比当前柱状低的第一个位置；从而构成以当前柱状的高度为高，以左右两边能延伸的宽度为宽的矩形。