思路：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。可以看这里的图。
这一题最直观的方式就是暴力法，对于每个柱体，向其左右延申，直到找到第一个比它矮的柱体：
public int largestRectangleArea(int[] heights) { int area = 0, n = heights.length; // 遍历每个柱子，以当前柱子的高度作为矩形的高 h， // 从当前柱子向左右遍历，找到矩形的宽度 w。 for (int i = 0; i < n; i++) { int w = 1, h = heights[i], j = i; while (--j >= 0 && heights[j] >= h) { w++; } j = i; while (++j < n && heights[j] >= h) { w++; } area = Math.max(area, w * h); } return area; }那么如何进行时间优化呢？栈是一种常用的空间换时间的数据结构，我们可以使用栈来操作，我们遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。
public int largestRectangleArea(int[] heights) { // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。 int[] tmp = new int[heights.length + 2]; System.arraycopy(heights, 0, tmp, 1, heights.length); Deque<Integer> stack = new ArrayDeque<>(); int area = 0; for (int i = 0; i < tmp.length; i++) { // 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」； // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。 // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积 while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) { int h = tmp[stack.pop()]; area = Math.max(area, (i - stack.peek() - 1) * h);//此时stack.peek()不再是上面的stack.peek()而是上面stack.peek()下面一个元素 } stack.push(i); } return area; }刚开始会思考这个栈的pop操作会对后续产生不好的影响吗，其实不会，栈中实际上存储的是递增的数据（栈顶最大），如果比栈顶小的元素到来，一定会先pop出比它大的元素，这时这个小元素入栈也是最大的了。
