代码随想录算法训练营第60天 | 84.柱状图中最大的矩形

单调栈章节理论基础：

https://leetcode.cn/problems/daily-temperatures/

84.柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

思路：

本题双指针的写法整体思路和42. 接雨水是一致的，但要比42. 接雨水 难一些。

难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
然后右边也是找到第一个小于该柱子的高度。通过示例里的图片应该很好理解。

所以需要循环查找，也就是下面在寻找的过程中使用了while，详细请看下面注释，整理思路在题解：42. 接雨水 中已经介绍了。

代码：

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] minLeftIndex =  new int[n];int[] minRightIndex = new int[n];// 初始化，防止下面while死循环。以及最后的求解minLeftIndex[0] = -1;// 记录每个柱子 左边第一个小于该柱子的下标for(int i=1;i<n;i++){int left = i - 1;while(left >= 0 && heights[left] >= heights[i])left = minLeftIndex[left];minLeftIndex[i] = left;}// 初始化，防止下面while死循环minRightIndex[n-1] = n;// 记录每个柱子 右边第一个小于该柱子的下标for(int i=n-2;i>=0;i--){int right = i + 1;while(right < n && heights[right] >= heights[i])right = minRightIndex[right];minRightIndex[i] = right;}// for(int i=0;i<n;i++){//     System.out.print(minLeftIndex[i] + " ");// }// System.out.println();// for(int i=0;i<n;i++){//     System.out.print(minRightIndex[i] + " ");// }// 求和int result = 0;for(int i=0;i<n;i++){int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] -1 );result = Math.max(sum,result);}return result;}
}