84. 柱状图中最大的矩形

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

思路：

首先，面积最大矩形的高度一定是 heights中的数。如果高度不是 heights中的数，那我们可以增加高度直到触及某个柱子顶部。

假设 h=heights[i]是矩形的高度，那么矩形的宽度最大是多少？我们需要知道：

• 在 i 左侧的小于 h 的最近元素的下标 left。
• 在 i 右侧的小于 h 的最近元素的下标 right。

比如示例 1（上图），选择 i=2 这个柱子作为矩形高，那么左边小于 heights[2]=5 的最近元素的下标为 left=1，右边小于 heights[2]=5 的最近元素的下标为 right=4。

那么矩形的宽度就是 right−left−1=4−1−1=2，矩形面积为 h⋅(right−left−1)=5⋅2=10。

枚举 i，计算对应的矩形面积，更新答案的最大值。

class Solution {
    public int largestRectangleArea(int[] heights) {
		int n = heights.length;
		int[] left = new int[n];
		Deque<Integer> stack = new ArrayDeque<>();
		for (int i = 0; i < n; i++) {
			int x = heights[i];
			while (!stack.isEmpty() && x <= heights[stack.peek()]){
				stack.pop();
			}
			left[i] = stack.isEmpty() ? -1 : stack.peek();
			stack.push(i);
		}

		int[] right = new int[n];
		stack.clear();
		for (int i = n - 1; i >= 0; i--) {
			int x = heights[i];
			while (!stack.isEmpty() && x <= heights[stack.peek()]){
				stack.pop();
			}
			right[i] = stack.isEmpty() ? n : 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;
    }
}