LeetCode刷题实战85：最大矩形-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大矩形，我们先来看题面：

https://leetcode-cn.com/problems/maximal-rectangle/

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

样例

解题

https://www.cnblogs.com/techflow/p/13359851.html

题解

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

暴力

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

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

第二种方法可以通过矩形的对角线上的两个点来确定，这种方法只适用于和坐标轴平行的矩形。比如下图当中，无论我们知道了(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的目的是为了弹出栈内所有的元素，因为只有出栈的元素会计算构成的面积，这样可以保证不会遗漏情况。

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

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode50-80题汇总，速度收藏！

LeetCode刷题实战81：搜索旋转排序数组 II

LeetCode刷题实战82：删除排序链表中的重复元素 II

LeetCode刷题实战83：删除排序链表中的重复元素

LeetCode刷题实战84：柱状图中最大的矩形