84.柱状图中最大的矩形

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

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

示例 1:

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

示例 2：

输入： heights = [2,4]
输出： 4

思路

单调栈 找到左边与 右边第一个更小元素, 然后按照当前元素高 * 左右之间的宽 取最大值 

本地单调栈的解法和接雨水的题目是遥相呼应的。

为什么这么说呢，42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。

单调栈的顺序总结：

 739. 每日温度 (opens new window)中求一个元素右边第一个更大元素，单调栈是递增的，84.柱状图中最大的矩形 (opens new window)求一个元素右边第一个更小元素，单调栈是递减的。

代码

class Solution {public int largestRectangleArea(int[] heights) {// 数组扩容，在头和尾各加入一个元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;Deque<Integer> st = new LinkedList<>();st.push(0);int len = heights.length;int S = 0;for(int i = 1; i <  heights.length; i++){if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else{while(!st.isEmpty() && heights[i] < heights[st.peek()]){int mid = st.pop();int start = st.peek();int end = i;S = Math.max(S, getS(heights, start, end, mid));}st.push(i);}}//res[i] 记录 i右侧第一个小于它的元素的索引, 循环数组记录return S;}public int getS(int [] height, int start, int end, int mid){int h = height[mid];int S = 0;for(int i = start + 1; i < end; i++){S += h;}return S;}
}

计算面积的小优化: 不再选择遍历 而是直接相乘

class Solution {public int largestRectangleArea(int[] heights) {// 数组扩容，在头和尾各加入一个元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;Deque<Integer> st = new LinkedList<>();st.push(0);int len = heights.length;int S = 0;for(int i = 1; i <  heights.length; i++){if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else{while(!st.isEmpty() && heights[i] < heights[st.peek()]){int mid = st.pop();int start = st.peek();int end = i;//(start, end)中的元素个数int w = end - start - 1;int h = heights[mid];S = Math.max(S, w * h);}st.push(i);}}//res[i] 记录 i右侧第一个小于它的元素的索引, 循环数组记录return S;}
}