当前位置:网站首页>单调栈-84. 柱状图中最大的矩形
单调栈-84. 柱状图中最大的矩形
2022-07-03 08:24:00 【later_rql】
1.题目
本题与42. 接雨水基本一致,建议两个结合着做
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/largest-rectangle-in-histogram
2.解题思路
解法一:动态规划
通过题目理解,是要求最大的两个柱子(也可能是单个柱子)的最大面积,可以考虑用动态规划来做
和42.接雨水那题有些类似,不同点在于,该题需要寻找当前柱子左边和右边小于其的柱子的索引,因此需要记录的是索引
方法二:单调栈
本题和42.接雨水的题目对应,接雨水是要求栈内元素从大到小排序,然后,取栈顶和栈顶的下一个元素以及要入栈的三个元素来接水!而本题是要求栈内元素从小到大排序,同样,栈顶和栈顶的下一个元素以及要入栈的三个元素来接水!
然后分析三种情况:
剩下就是分析清楚如下三种情况:
- 情况一:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况(出现最大面积)
- 情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
- 情况三:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
3.代码
方法一:动态规划
public int largestRectangleArea(int[] heights) {
int length = heights.length;
int[] minLeftIndex = new int [length];
int[] maxRigthIndex = new int [length];
// 记录左边第一个小于该柱子的下标
minLeftIndex[0] = -1 ;
for (int i = 1; i < length; i++) {
int t = i - 1;
// 这里不是用if,而是不断向右寻找的过程
while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
minLeftIndex[i] = t;
}
// 记录每个柱子 右边第一个小于该柱子的下标
maxRigthIndex[length - 1] = length;
for (int i = length - 2; i >= 0; i--) {
int t = i + 1;
while(t < length && heights[t] >= heights[i]) t = maxRigthIndex[t];
maxRigthIndex[i] = t;
}
// 求和
int result = 0;
for (int i = 0; i < length; i++) {
int sum = heights[i] * (maxRigthIndex[i] - minLeftIndex[i] - 1);
result = Math.max(sum, result);
}
return result;
}
方法二:单调栈
int largestRectangleArea(int[] heights) {
Stack<Integer> st = new Stack<Integer>();
// 数组扩容,在头和尾各加入一个元素
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;
st.push(0);
int result = 0;
// 第一个元素已经入栈,从下标1开始
for (int i = 1; i < heights.length; i++) {
// 注意heights[i] 是和heights[st.top()] 比较 ,st.top()是下标
if (heights[i] > heights[st.peek()]) {
st.push(i);
} else if (heights[i] == heights[st.peek()]) {
st.pop(); // 这个可以加,可以不加,效果一样,思路不同
st.push(i);
} else {
while (heights[i] < heights[st.peek()]) {
// 注意是while
int mid = st.peek();
st.pop();
int left = st.peek();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = Math.max(result, w * h);
}
st.push(i);
}
}
return result;
4.性能
方法一:动态规划
- 时间复杂度:O(n)
- 空间复杂度:O(n)
方法二:单调栈
- 时间复杂度:O(n)
- 空间复杂度:O(n)
边栏推荐
- Editor Extensions
- Introduction to Base64 coding
- C#课程设计之学生教务管理系统
- Detailed explanation of all transfer function (activation function) formulas of MATLAB neural network
- MySQL 8
- Redis cluster series 4
- P1596 [USACO10OCT]Lake Counting S
- Haproxy+kept build 01
- Graphics_ Games101/202 learning notes
- Classes and objects
猜你喜欢
GIS实战应用案例100篇(七十八)-多规合一数据库设计及数据入库
CLion-Toolchains are not configured Configure Disable profile问题解决
C#课程设计之学生教务管理系统
Basic operation and process control 2
Animation_ IK overview
Solution détaillée de toutes les formules de fonction de transfert (fonction d'activation) du réseau neuronal MATLAB
[set theory] order relation (the relation between elements of partial order set | comparable | strictly less than | covering | Haas diagram)
Unity editor expansion - draw lines
Notes on understanding applets 2022/7/3
Youyou1 of xlua knapsack system
随机推荐
Go resolve ID card
matlab神经网络所有传递函数(激活函数)公式详解
[audio and video] ijkplayer error code
Advanced OSG collision detection
P1596 [USACO10OCT]Lake Counting S
Intersectionpicker in osgearth
使用base64编码传图片
Redis data structure
详解sizeof、strlen、指针和数组等组合题
【音视频】ijkplayer错误码
Xlua task list youyou
Osgearth north arrow display
php-fpm软件的安装+openresty高速缓存搭建
VIM learning notes from introduction to silk skating
Mall management system of database application technology course design
数据的存储
redis集群系列四
About Wireshark's unsuccessful installation of npcap
About the problem that the editor and the white screen of the login interface cannot be found after the location of unityhub is changed
Transplantation of freetype Library