专栏首页TechFlowLeetCode 85 | 如何从矩阵当中找到数字围成的最大矩形的面积?

LeetCode 85 | 如何从矩阵当中找到数字围成的最大矩形的面积?

今天是LeetCode专题53篇文章,我们一起来看看LeetCode中的85题,Maximal Rectangle(最大面积矩形)。

今天的这道题目和上一篇文章讲的Largest Rectangle in Histogram这题有一定的相似,所以如果没有看过上一篇文章的同学,建议先移步观看一下上一篇。

LeetCode 84 | 单调栈解决最大矩形问题

85题的官方难度是Hard,点赞2757,反对69,通过率37.2%左右。它的情况和84题非常相似,点赞比很高,然后通过率也差不多。虽然它是84题的变形题,但是整体的题目质量还是很高的,没有因为这一点被诟病。那么和84题相比,究竟它的变动在哪里呢,让我们一起来看题目吧。

题意

给定一个只包含0和1的数字矩阵,要求在这个矩阵当中找到一个由1组成的最大面积的矩形,返回这个面积。

我们来看个样例:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

答案是6,是这一块1围成的矩形:

题解

还是老规矩,我们从最简单的方法入手,一点点推导出最佳的思路。

暴力

首先最简单的当然是暴力,这题让我们寻找一个矩形,直接寻找矩形是有点麻烦的。计算机程序不像人眼,可以直接获取到图形相关的信息,计算机不行,只能获得单个位置的信息。所以我们让程序直接判断矩形是不现实的,但我们可以通过特征点来锁定矩形,这个也是业内常用的套路。

锁定一个矩形的方法一般有两种,第一种是用矩形的中心点和长宽来确定。这一种在各种图像识别和目标检测算法当中经常用到,模型预测的结果就是图像中心点的坐标以及长宽的长度。

第二种方法可以通过矩形的对角线上的两个点来确定,这种方法只适用于和坐标轴平行的矩形。比如下图当中,无论我们知道了(x2, y2), (x3, y3)还是(x1, y1), (x4, y4),我们都可以将这个矩形确定下来。

有了确定矩形的方法之后,我们通过暴力法来求解就简单了。我们通过这些值来枚举所有可能构成的矩形,然后依次遍历矩形中的每一个元素,来判断它们是否全是1,如果是否的话,那么就排除,否则则用来更新答案。

这种方法固然可行,但是估算一下,差不多应该是的规模,显然是我们不能接受的。

分析问题

在暴力解法当中我们遇到了时间复杂度的困难,我们想要优化就必须要解决复杂度的问题,复杂度的问题怎么解决呢?干想肯定是不行的,我们需要转变一下思路,寻找一下突破口。

我们枚举的复杂度规模这么高是因为我们遍历了所有矩形,遍历矩形本身就是一个时间复杂度开销非常大的举动。如果不想遍历矩形,还有什么方法可以得出最大面积呢?如果我们联想一下上一题很容易得出答案。

在上一题84题当中,题目给出的是一个个竖直类型的矩形,要求这些矩形组合当中能够找到的最大面积。

在这题当中我们可以对01的数字矩阵也做这么一个类似的变形,将从底部开始连续延伸的1的数量看成是竖直摆放的矩形的高度,这样我们这题就可以使用上一题的思路进行求解了。

  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]

比如说上面这个矩阵就可以转变为[4, 0, 0, 3, 0],其实就是我们一列一列看,从最低处往上连续的1的数量。但是这样找到的面积最大值是4,并不是答案的6,原因是因为我们寻找的底层不对,并不一定以最后一行作为底面得到的面积最大。所以我们需要遍历作为底层的行,然后用这种方法寻找最大面积,全局当中找到的最大面积就是答案。

在上一题我们计算矩形面积的时候用到了两个单调栈,分别计算了某一个高度向左、向右能够延伸到的最远距离,其实这并没有必要。因为我们用一个栈也可以同时计算出两边的边界。举个例子:[1, 3, 6, 7],当前元素是5。我们需要把6,7出栈,5入栈。我们知道了5的左边界是3,但仔细想一想,对于7来说,我们知道了它的左右边界。7的左边界是6,右边界是5。也就是说对于栈顶的元素而言,它的左边界是stack[top-1],右边界是当前的位置i,宽就是i - stack[top-1] - 1。

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        # 求出行数n和列数m
        n = len(matrix)
        if n == 0:
            return 0

        m = len(matrix[0])
  # 存储每一层的高度
        height = [0 for _ in range(m+1)]
        res = 0
        # 遍历以哪一层作为底层
        for i in range(n):
            sk = [-1]
            for j in range(m+1):
                # 计算j位置的高度,如果遇到0则置为0,否则递增
                h = 0 if j == m or matrix[i][j] == '0' else height[j] + 1
                height[j] = h
                # 单调栈维护长度
                while len(sk) > 1 and h < height[sk[-1]]:
                    res = max(res, (j-sk[-2]-1) * height[sk[-1]])
                    sk.pop()
                sk.append(j)
        return res

总结

乍一看这道题好像非常复杂,但是当我们对它进行分析和变形之后,它又变回了普通的单调栈的应用题。在单调栈的使用当中,有两个细节,一个细节是栈在初始化的时候插入了-1,插入-1是作为一个标兵,也就是所有情况能够达到的最左侧的边界。另一个细节是维护结束的时候插入了0,插入0的目的是为了弹出栈内所有的元素,因为只有出栈的元素会计算构成的面积,这样可以保证不会遗漏情况。

除了上面提到的之外,还有其他的一些细节,比如数组的创建的长度,还有矩形面积的计算公式等等。很多时候算法之所以难以实现,也正是因为需要考虑的细节很多,整体的逻辑不是非常清楚,需要我们进行大量的思考。总体来说,这是一道非常优秀的问题,值得大家仔细钻研。

本文分享自微信公众号 - TechFlow(techflow2019),作者:梁唐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单调栈巧解柱状图最大矩形

    这几天群里打卡的几道题都是十分经典的面试题,经典是因为这些题都是一题多解的。在这些高效的解法中,单调栈是一个很有技巧的解法,所以这一次我们来聊聊这个单调栈。

    TechFlow-承志
  • LeetCode 84 | 单调栈解决最大矩形问题

    今天是LeetCode专题第52篇文章,我们一起来看LeetCode第84题,Largest Rectangle in Histogram(最大矩形面积)。

    TechFlow-承志
  • Python | 详解Python中的协程,为什么说它的底层是生成器?

    我们曾经在golang关于goroutine的文章当中简单介绍过协程的概念,我们再来简单review一下。协程又称为是微线程,英文名是Coroutine。它和线...

    TechFlow-承志
  • 单调栈巧解柱状图最大矩形

    这几天群里打卡的几道题都是十分经典的面试题,经典是因为这些题都是一题多解的。在这些高效的解法中,单调栈是一个很有技巧的解法,所以这一次我们来聊聊这个单调栈。

    TechFlow-承志
  • 用matlab打造属于自己屏幕录像工具

    现在网上的录屏软件可谓是五花八门,各有特色,收费免费的都有。可聪明的你,有没有想过用matlab打造一款属于自己的录屏工具呢?是的,没有看错,用matlab打造...

    艾木樨
  • 谈谈系统监控应该怎么做

    什么样的系统才算成功的呢?很显然,能让系统关联方满意的系统才算是成功的,想要做好这点,必须做好监控。监控是系统的眼睛,它能让我们及时发现问题,不...

    公众号_松华说
  • 如何在Ubuntu 14.04上使用Nginx和Php-fpm安全地托管多个网站

    众所周知,LEMP堆栈(Linux,nginx,MySQL,PHP)为运行PHP站点提供了无与伦比的速度和可靠性。但是,这种流行的堆栈的其他特性,如安全性和隔离...

    angel_郁
  • NVDLA中Winograd卷积的设计

    卷积神经网络中的三维卷积(后文简称为卷积)计算过程可以表示如下,将这种直接通过原始定义计算卷积的方式称为直接卷积(Direct Convolution)。

    sea-wind
  • 我赵永强又回来了:单散、认证与数签(五上)

    作为一个后知后觉的人,我也是昨天看到有人在光天化日之下公开批判我【尥蹶子】【不写公众号】,你们先感受下:

    老李秀
  • HttpInvoker运作原理

    HttpInvoker是常用的Java同构系统之间方法调用实现方案,是众多Spring项目中的一个子项目。顾名思义,它通过HTTP通信即可实现两个Java系统之...

    哲洛不闹

扫码关注云+社区

领取腾讯云代金券