思路： 比如当前柱子的高度是h，这个问题的本质就是分别算出当前柱子左右两侧，第一个小于h柱子的位置，左侧leftMin如果比0小就是-1，右侧rightMin比索引大就是index+1·，最后当前柱子的最大面积就是（rightMin-leftMin-1）*h,然后比较每个柱子的最大柱子，得到最终结果。   首先最先想到的是暴力法，根据两层循环遍历，算出每个柱子的最大面积。   单调栈法： 首先补充下单调栈的概念： 从栈尾到栈顶递减就是单调递减栈； 从栈尾到栈懂递增就是单调递增栈。 单调递增栈，可以找到左右两边第一个比他小的元素； 单调递减栈，可以找到左右两边第一个比他大的元素。 对于每个元素，其有且仅有一次插入，最多出现一次删除，故其时间复杂度为O（n）。   当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素     用单调递增栈解决当前问题，因为要找出左右两侧第一个比他小的元素的位置。遍历到一个元素的时候，如果当前栈不为空，就比较栈顶元素和当前元素i的大小，如果i比栈顶小，那栈顶元素就是右侧第一个比i小的元素，弹出栈顶元素，最后栈为空或者当前元素大于栈顶元素就跳出循环；判断栈是否为空，为空说明当前元素左侧没有比他小的，不为空就是栈顶是右侧第一个比他小的元素。最后栈中还剩数据，说明这些元素的右侧没有比他小的。     对于栈里的元素来说，当前准备入栈的元素就是他们右侧，如果有元素弹出，当前准备入栈的元素就是弹出元素右侧第一个比他小的； 对于准备入栈的元素来说，栈里的元素就是他的左侧，如果在当前元素入栈的时候栈为空，说明左侧没有比他小的，如果栈不为空，栈里都是比他小的元素，那么栈顶就是右侧第一个比他小的元素。   一次遍历就可以拿到每个位置左右两侧第一个比他小元素的索引。     题目： 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。   求在该柱状图中，能够勾勒出来的矩形的最大面积。    解答： public class LargestRectangleArea_84 { public static int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; int[] right = new int[n];   Deque<Integer> stack = new ArrayDeque<Integer>(); for(int i=0;i<heights.length;i++) { //单调递增栈，找出右边第一个小于当前元素的值 //把数组索引存在stack中，当栈不为空且当前栈顶的节点小于当前数组时候， //入栈的时候，如果栈为空，说明他的左侧没有比当前入栈位置要小的元素，左侧比他小的位置就是-1， //如果栈中有元素的时候，栈顶的数就是左侧第一个比他小的数 while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]) { right[stack.pop()]=i; } //判断栈是否为空，为空说明当前元素左侧没有比他小的，不为空就是栈顶是右侧第一个比他小的元素。 left[i]=stack.isEmpty()?-1:stack.peek(); stack.push(i); } //栈中还剩数据，说明栈中数据右侧没有比他小的，全部填充为数组长度 while(!stack.isEmpty()) { right[stack.pop()]=heights.length; }   int max=0; for(int i=0;i<left.length;i++) { max=Math.max(max, (right[i]-left[i]-1)*heights[i]); }       return max; }   public static void main(String[] args) { int[] array= {6, 7, 5, 2, 4, 5, 9, 3}; largestRectangleArea(array); }   }