代码随想录 84.柱状图中最大的矩形

思路：本题和接雨水是遥相呼应的题目。原理上有很多相同的地方，但细节上又有差异，可以加深对单调栈的理解。

（一）方法一：暴力解法，超时。

（二）方法二：双指针解法。本题要记录每个柱子左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度，因此需要使用while循环查找。

附代码：

class Solution { public int largestRectangleArea(int[] heights) { int len = heights.length; int[] minLeftIndex = new int[len]; //记录每个柱子左边第一个比它矮的柱子下标 int[] minRightIndex = new int[len]; //记录每个柱子右边第一个比它矮的柱子下标 //记录左边第一个小于该柱子的下标 minLeftIndex[0] = -1; for(int i = 1;i < len;i++){ int t = i - 1; //这里不是用if，而是不断向右寻找的过程 while(t >= 0 && heights[t] >= heights[i]){ t = minLeftIndex[t]; //跳跃式查找，不是逐个比较。因为如果heights[t]比当前柱子高，那么比heights[t]更高的左边柱子也肯定比当前柱子高。这保证了O(n)的时间复杂度。 } minLeftIndex[i] = t; } //记录每个柱子右边第一个小于该柱子的下标 minRightIndex[len - 1] = len; for(int i = len - 2;i >= 0;i--){ int t = i + 1; while(t < len && heights[t] >= heights[i]){ t = minRightIndex[t]; } minRightIndex[i] = t; } //求和 int res = 0; for(int i = 0;i < len;i++){ int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1); res = Math.max(res,sum); } return res; } }

（三）方法三：单调栈。

1.本题和42.接雨水是遥相呼应的，因为接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

2.单调栈的顺序：因为是找每个柱子左右两边第一个小于该柱子的柱子，因此顺序为单调递减（从栈头到栈底）。

举例如下图所示，只有栈里是从大到小的顺序，才能保证可以从栈顶元素找到左右两边第一个小于栈顶元素的柱子：

3.栈顶元素、栈顶的下一个元素以及要入栈的元素就组成了要求最大面积的高度和宽度。

4.分析三种情况：

（1）情况一：当前遍历的元素的heights[i]大于栈顶元素heights[stack.peek()]的情况。

（2）情况二：当前遍历的元素的heights[i]等于栈顶元素heights[stack.peek()]的情况。

（3）情况三：当前遍历的元素的heights[i]小于栈顶元素heights[stack.peek()]的情况。

5.在heights数组开头和末尾，都加了一个元素0。

（1）末尾加0：如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后都是单调递减，一直没有走情况三计算结果的那一步，所以最后输出的就是0，如下图所示。

而在结尾加上0，就会让栈里的所有元素走到情况三的逻辑。

（2）开头加0：如果数组本身是降序的，例如[8,6,4,2]，在8入栈后，6开始与8进行比较，此时可以得到mid(8)、right(6)，但是得不到left。这是因为栈将8弹出之后，栈里就没有元素了，为了避免空栈取值，会直接跳过计算结果的逻辑。之后又将6加入栈（此时8已经弹出了），然后就是4与栈口元素6进行比较，周而复始，计算的最后结果res就是0，如下图所示。

（3）因此需要在heights数组前后各加一个元素0。

附代码：

class Solution { public int largestRectangleArea(int[] heights) { LinkedList<Integer> stack = new LinkedList<>(); //数组扩容，在头和尾各加入一个元素 int[] newHeights = new int[heights.length + 2]; newHeights[0] = 0; newHeights[newHeights.length - 1] = 0; for(int i = 0;i < heights.length;i++){ newHeights[i + 1] = heights[i]; } heights = newHeights; stack.push(0); int res = 0; // 第一个元素已经入栈，从下标1开始 for(int i = 1;i < heights.length;i++){ //heights[i]是和heights[stack.peek()]进行比较的，stack.peek()是下标 if(heights[i] > heights[stack.peek()]){ stack.push(i); }else if(heights[i] == heights[stack.peek()]){ stack.pop(); stack.push(i); }else{ while(heights[i] < heights[stack.peek()]){ int mid = stack.peek(); stack.pop(); int left = stack.peek(); int right = i; //此时left是左边第一个比mid矮的元素，right是右边第一个比mid矮的元素 //(left,right)左开右开区间内的柱子都 >= mid的高度 //计算(left,right)区间的宽度 int w = right - left - 1; //(left,right)区间的高度就是最矮点的高度，即mid的高度 int h = heights[mid]; res = Math.max(res,w * h); } stack.push(i); } } return res; } }

单调栈精简版：

System.arraycopy()的用法：System.arraycopy(Object src,int srcPos,Object dest,int destPos,int length)。

（1）src：源数组。

（2）srcPos：源数组要复制的起始位置。

（3）dest：目的数组。

（4）destPos：目的数组放置的起始位置。

（5）length：复制的长度。

附代码：

class Solution { public int largestRectangleArea(int[] heights) { int[] newHeight = new int[heights.length + 2]; System.arraycopy(heights,0,newHeight,1,heights.length); //在数组前后各加一个0 newHeight[heights.length + 1] = 0; newHeight[0] = 0; LinkedList<Integer> stack = new LinkedList<>(); stack.push(0); int res = 0; for(int i = 1;i < newHeight.length;i++){ while(newHeight[i] < newHeight[stack.peek()]){ int mid = stack.pop(); int w = i - stack.peek() - 1; int h = newHeight[mid]; res = Math.max(res,w * h); } stack.push(i); } return res; } }