LeetCode 84. 柱状图中最大的矩形
2020-04-05 16:02:08来源:博客园 阅读 ()
LeetCode 84. 柱状图中最大的矩形
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 84. 柱状图中最大的矩形
题目
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为?[2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为?10?个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
思路1-直接双层遍历,暴力解题
步骤:
- 外层循环每次选定i作为中心;
- 内层循环每次以i作为中心向两侧扩展,扩展的高不能低于i;
- 计算可扩展的最大面积,计算所有i扩展面积中的最大值;
效率:
- 时间复杂度:O(n2)
- 空间复杂度O(1)
思路2-使用单调栈
步骤:
- 新建栈,从左向右遍历入栈,入栈的条件是,当前即将入栈的柱子高度必须不低于当前栈顶的柱子高度,即柱子是单调递增的;
- 若当前柱子低于栈顶的柱子高度,说明之前的柱子高度不能再扩展了,需要从栈顶依次弹出并计算以每个栈元素为高时的矩形面积,直到栈顶柱子高度不高于当前柱子高度;
- 在2中计算到当前栈顶柱子高度不高于当前即将入栈的柱子高度时,当前柱子入栈;
- 上面的步骤有一个缺陷:若所有的柱子都是递增的,则矩形的面积就不曾计算过,所以还需要再加一个第4步;
- 在1新建栈时就压入一个垫底的数-1,在完成123步骤后,再以2的逻辑处理栈中的所有元素直到栈中只剩-1;
图解:
总结:单调栈也是算法中一个很有用的特性,需要多熟悉学习应用
算法源码示例
package leetcode;
import java.util.Stack;
/**
* @author ZhouJie
* @date 2020年4月4日 下午12:51:29
* @Description: 84. 柱状图中最大的矩形
*
*/
public class LeetCode_0084 {
}
class Solution_0084 {
/**
* @author: ZhouJie
* @date: 2020年4月4日 下午1:17:32
* @param: @param heights
* @param: @return
* @return: int
* @Description: 1-一次遍历,遍历中左右扩展,实际算法复杂度为O(n2)
*
*/
public int largestRectangleArea_1(int[] heights) {
int len = 0;
if (heights == null || (len = heights.length) == 0) {
return 0;
}
int maxArea = 0;
for (int i = 0; i < len; i++) {
if (heights[i] != 0) {
int l = i, r = i, h = heights[i];
while (l > 0 && heights[l - 1] >= h) {
l--;
}
while (r < len - 1 && heights[r + 1] >= h) {
r++;
}
maxArea = Math.max(maxArea, h * (r - l + 1));
}
}
return maxArea;
}
/**
* @author: ZhouJie
* @date: 2020年4月4日 下午1:43:01
* @param: @param heights
* @param: @return
* @return: int
* @Description: 2-单调栈
*
*/
public int largestRectangleArea_2(int[] heights) {
int len = 0;
if (heights == null || (len = heights.length) == 0) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
int maxArea = 0;
for (int i = 0; i < len; i++) {
while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (len - stack.peek() - 1));
}
return maxArea;
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12636834.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash