给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
本题是比较难的一道题，一开始做可能会摸不着头脑。但是一旦掌握思想其实写起来代码是不复杂的。
一切的一切都要思考一下，如果不用任何算法，我们就想要知道这个面积该怎么求？
我们是不是会观察一个矩形旁边的位置是否比他矮，如果比他矮，那矩形就以它为高宽为1，来计算，然后每个矩形逐一进行计算，通过左边界的值和右边界的值差值来乘以这个矩形的高。这其实就是暴力算法的根据。
我们转化题目，其实就是求每一柱子它的左边能达到比他更高的点和它的右边能达到比他更高的点。如果我们把每个矩形的两个位置点给算出来，那答案其实就已经出来了，每个矩形进行求最大值就可以了。
那如何求左边或者右边的边界值呢？
我们从左往右遍历，我们可以发现，我们一定肯定可以确定左边界。
我们可以用一个列表保存节点，当我们从左往右遍历的时候，每次遇见高度比当前节点高的就保存下来，那就肯定能确定左边界就是自己了，如果遇见高度比当前节点低的，就一直往前遍历，直到空或者比当前节点更低的，在这个过程中我们可以用栈来帮助我们。
我们从右往左遍历，同样道理，可以确定右边界。
那这样答案也就出来了。
其实做这道题最重要的思想就是我们要通过暴力算法去思考出问题本质，然后观察出如何简化代码，利用空间换时间的思想。
在这个过程中其实是可以优化我们的确定左右边界的代码的，代码如下：
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Stack<Integer> stack = new Stack<>();
int []left = new int[n];
int []right = new int[n];
Arrays.fill(right,n);
for (int i = 0; i < n; i++){
while ( !stack.isEmpty() && heights[stack.peek()] > heights[i]){
right[stack.pop()] = i;
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++){
ans = Math.max(ans,(right[i] - left[i] - 1) * heights[i] );
}
return ans;
}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
