网站开发页面,网站模板文件下载,wordpress 安装平台,施工企业资质类别单调栈章节理论基础#xff1a;
https://leetcode.cn/problems/daily-temperatures/
84.柱状图中最大的矩形
题目链接#xff1a;https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
思路#xff1a;
本题双指针的写法整体思路和42. 接雨水是一…单调栈章节理论基础
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 i1;in;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 in-2;i0;i--){int right i 1;while(right n heights[right] heights[i])right minRightIndex[right];minRightIndex[i] right;}// for(int i0;in;i){// System.out.print(minLeftIndex[i] );// }// System.out.println();// for(int i0;in;i){// System.out.print(minRightIndex[i] );// }// 求和int result 0;for(int i0;in;i){int sum heights[i] * (minRightIndex[i] - minLeftIndex[i] -1 );result Math.max(sum,result);}return result;}
}
