LeetCode | 85. 最大矩形
发布日期:2021-06-27 12:55:22
浏览次数:31
分类:技术文章
本文共 894 字,大约阅读时间需要 2 分钟。
LeetCode | 85. 最大矩形
一、题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。示例1 :
示例2 : 示例3 : 示例4 : 示例5 : 提示:二、题解及思路
对于解答这道题,我们最开始想到的解法就是:列举所有的矩形(列举所有可能的矩形的左上角坐标和右下角坐标),然后获取得到最大面积的矩形。但是这种算法的时间复杂度太高,无法通过所有的测试用例。
这里提供两种解法,如果有更好的解法,欢迎大家留言~~
2.1、方法一: 柱状图中最大的矩形-优化版暴力算法复用
还记得上一期所讲的【柱状图中最大的矩形-优化版暴力算法】吗?这里不细说,可以参考阅读。
- 要求:面积 = 长 宽
- 思路:
- 首先先行进行遍历,获取并记录每行连续1的数量。如下图:
- 计算矩形长度和宽度:对于矩阵中的每个点,按照列向上进行遍历,获取该遍历范围内的最小值,作为矩形的“长”,而遍历的行数就是矩形的“宽”。如下图: 因此,area = width * (i-k+1) 。width即为按列遍历中的最小数值。
示例代码(Java):
执行结果:
复杂度分析:
- 时间复杂度O(m2n):统计连续1的个数:O(mn);计算以矩阵点为右下角的矩阵面积:O(m2n),因此,时间复杂度为O(m2n)。
- 空间复杂度O(mn):需要rows[m][n]来存储统计连续1的数量。
如果你参考了 ,可以发现其实这里只是把矩阵的长宽获取变成了对列和行的遍历统计。
2.2、方法二:栈
在 中,我们不仅用了优化的暴力算法,还用到了一种比较常见的数据结构,将算法的时间和空间复杂度都降低了一个计算单位。那么这里是否也可以使用栈来实现呢?同样我们可以将每个计算后的矩阵面积进行存储,从而降低对所有矩阵点的遍历,降低算法的时间复杂度。具体栈操作与【柱状图中最大的矩形】中的栈方法相似,这里不在细说。它其实就是对每一列使用来计算矩形的面积。直接上代码噢~~
示例代码(Java):
执行结果:
复杂度分析:
- 时间复杂度:O(mn)
- 空间复杂度:O(n)
转载地址:https://blog.csdn.net/weixin_43452424/article/details/111824427 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月01日 20时15分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Unity中解决“SetDestination“ can only be called on an active agent that has been placed on a NavMesh
2019-04-27
Unity中的刚体
2019-04-27
Unity中的坐标转换
2019-04-27
Unity中为什么不能对transform.position.x直接赋值?
2019-04-27
Unity中物体移动方法详解
2019-04-27
使用对象池优化性能
2019-04-27
Lua(一)——Lua介绍
2019-04-27
Lua(二)——环境安装
2019-04-27
Unity中父子物体的坑
2019-04-27
基础知识——进位制
2019-04-27
Lua(十二)——表
2019-04-27
Lua(十三)——模块与包
2019-04-27
Lua(四)——变量
2019-04-27
Lua(十四)——元表
2019-04-27
Lua(十五)——协同程序
2019-04-27
Lua(十六)——文件
2019-04-27
Lua(十七)——面向对象
2019-04-27
Lua(十八)——错误处理,垃圾回收
2019-04-27
xLua(一)——介绍
2019-04-27
xLua(二)——下载
2019-04-27