题目描述

题目链接

给定一个仅包含 0 和 1 ，大小为 n*m 的二维二进制矩阵，找出仅包含 1 的最大矩形并返回面积。

数据范围：1 ≤ n,m ≤200, 保证输入的矩形中仅含有 0 和 1

返回值描述

矩阵中仅包含 1 的最大矩形的面积

示例

输入:

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

形成的最大矩形如下图所示：

输出:

8

核心思想

首先这道题目可以分成两步走,首先将数组的每一行处理成直方图，直方图的高度就是每一列元素对应的高度，而这个高度就是连续1的长度，例如图中黄色的就是第一行的直方图：

那么只需要在这个直方图上求解出当前最大矩形面积，用红色表示

然后按行依次遍历就可以得到每行直方图的最大矩阵，再对其取最大值就可以得到数组的最大矩阵面积，如下图所示，可以看出红色最大面积就是8。本质上是对矩阵中的每行依次执行直方图最大矩阵算法。

题解

解题思路一

1. 那么第一步就是将数组的每一行处理成直方图，这一步得到每一行高度思路有点dp的味道：从上层得到下一层能建立的柱体的最大高度，可以用一个heights记录前一行的最大高度，如果数组对应的元素是1，就在之前的最大高度基础上加一，不然就置为0，用公式表示就是：

2. 获得该行的直方图之后，就可以在heights上求解该行的直方图最大矩阵面积，例如题目中的第三行，得到的heights = [3, 2, 3, 2, 1]，对应的直方图如下所示：

3. 观察这个矩阵，最简单的暴力方法就是枚举每一列，每一列的高度就是矩形的高度 h。随后从这根柱子开始向两侧延伸，直到遇到高度小于 $hh$ 的柱子，就确定了矩形的左右边界，左右边界之间的宽度计为 $ww$，对应的面积为 $w\times hw\times h$。最后取这些列的最大值，就可以得到该行的最大面积，然后遍历所有行，就可以得到这个数组的最大面积。

图解分析

特定列矩阵面积动画演示

码上行动

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型
#
from typing import List

class Solution:
    def maximalRectangle(self , matrix: List[List[int]]) -> int:
        # write code here
        # 获取矩阵的长宽
        rows = len(matrix)
        # 如果是空，直接返回
        if rows == 0:
            return 0 
        cols = len(matrix[0])
        heights = [0 for _ in range(cols)]
        res = 0
        # 预处理矩阵
        for i in range(rows):
            for j in range(cols):
                heights[j] = heights[j] + 1 if matrix[i][j] == 1 else 0
                
            res = max(res, self.largest_rectangle_area(heights))
            
        return res
    
    def largest_rectangle_area(self, heights: List[int]) -> int:
        # 判断heights，为空直接返回0
        if len(heights) == 0:
            return 0
        n = len(heights)
        res = 0
        for mid in range(n):
            # 枚举高
            height = heights[mid]
            left, right = mid, mid
            # 确定左右边界
            while((left - 1) > 0 and heights[left - 1] >= height):
                left -= 1
            while((right + 1) < n and heights[right + 1] >= height):
                right += 1
            # 计算面积
            res = max(res, (right-left+1)*height)
        return res

复杂度分析

• 时间复杂度，预处理成直方图的时间复杂度从两次循环中易得为$O(m\ast n)O(m*n)$，而largest_rectangle_area算法,首先需要 $O(m)O(m)$ 的时间枚举，然后求解最大面积的时间复杂度为$O(n^2)O(n^2)$,所以总的时间复杂度为 $O(m\ast n)+O(n^2)\ast O(m)=O(m\ast n^2)O(m*n)\; +\; O(n^2)*O(m)\; =\; O(m*n^2)$。
• 空间复杂度，定义了一个heights，所以空间复杂度为$O(m)O(m)$。

解题思路二

方法一中，首先将输入拆分成一系列的直方图，只需要计算每个直方图中的最大面积，就可以计算出数组中的最大矩阵面积。而可以优化的地方主要在于第二步的largest_rectangle_area算法，暴力求解的方法时间复杂度过高，可以采用单调栈的思想，首先简单介绍一下单调栈：

• 单调栈分为单调递增栈和单调递减栈，单调递增栈即栈内元素保持单调递增的栈，单调递减栈则相反。

这题主要用的是单调递增栈，对于输入[2, 1, 5, 6, 2, 3]来说，在观察第一个元素时，由于不知道其右边元素是否比它大，所以可将其先记录下来

然后考察下一个元素，在考察到下一个元素时，发现其值 $11$ 小于第一个元素 $22$ 。因此，这时可以确定第一个元素的最大矩形面积，用粉红色表示。

在确定第一个元素面积后，第一个元素就可以无视了，用白块表示：

然后对于第二元素，向后遍历，如果下一个元素大于当前的栈顶元素，就加入；如果不大于，就可以确定栈顶元素的最大面积，因为是个单调栈，栈顶元素一定是最大的，也就是说栈顶肯定大或者等于栈内元素,分别加入 $33$ ，$44$ 元素。

那么当出现新加入元素比栈顶元素小的情况，由于之前记录的高度是逐渐递增的，所以其左侧边界可以确定；同时，由于当前考察的元素高度小于栈顶元素，其右侧边界也确定，例如加入 $22$ 时，高度为 $44$ 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 $33$ 的柱形和高度为 $22$ 的柱形之间的，它的高度是 $44$，宽度是 $11$ ，面积也确定了。

由于 $22$ 还是比栈顶元素 $33$ 小，所以 $33$ 对应的面积也可以确定了，它是夹在高度为 $11$ 和高度为 $22$ 的两个柱形之间，高度是 $33$，宽度是 $22$。

确定好之后，都标记成白块，后续可以无视这些确定的元素，算法中则体现为元素在stack弹出了。

通过前述的步骤我们发现了，只要是遇到了要加入栈的元素柱形的高度比它上一个柱形的高度严格小的时候，之前的某些元素的宽度就可以确定了，并且确定的柱形宽度的顺序是从右边向左边。而我们在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这该元素对应的最大宽度。

值得注意的是在确定宽度的时候，右边严格小是一定能满足的，那么我们所需要保证的就是左边的严格小，简单来说就是向左找的时候一定要找到第一个严格小于我们要确定的那个元素柱形的高度的下标。这个时候中间那些相等的柱形其实就可以当做不存在一样，因为他们的矩阵面积是一样的。

最后遍历到最后一个元素 $33$ ,加入栈中。

一次遍历完成以后。接下来考虑栈里的元素全部出栈，首先看栈顶元素，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1，面积计算然后变成白块

然后看下标4的元素，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4，同理。

最后只有下标1的元素，说明是最小的，宽度就是数组的长度，至此所有面积也得出来了，取最大值就是该直方图的最大矩形面积。

图解分析

将上述过程用动画演示如下

码上行动

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型
#
class Solution:
    def maximalRectangle(self , matrix: List[List[int]]) -> int:
        # write code here
        # 获取矩阵的长宽
        rows = len(matrix)
        # 如果是空，直接返回
        if rows == 0:
            return 0 
        cols = len(matrix[0])
        heights = [0 for _ in range(cols)]
        res = 0
        # 预处理矩阵
        for i in range(rows):
            for j in range(cols):
                heights[j] = heights[j] + 1 if matrix[i][j] == 1 else 0
                
            res = max(res, self.largest_rectangle_area(heights))
            
        return res
    
    def largest_rectangle_area(self, heights: List[int]) -> int:
        # 判断heights，为空直接返回0
        if len(heights) == 0:
            return 0
        
        n = len(heights)
        res = 0

        stack = []

        for i in range(n):
            # 判断stack不为空 并且加入元素比栈顶小
            while len(stack) > 0 and heights[i] < heights[stack[-1]]:
                # 处理栈顶元素
                cur_height = heights[stack.pop()]
                # 找到左边第一个严格小于的元素
                while len(stack) > 0 and cur_height == heights[stack[-1]]:
                    stack.pop()
                
                # 确定宽度
                if len(stack) > 0:
                    cur_width = i - stack[-1] - 1
                else:
                    cur_width = i

                res = max(res, cur_height * cur_width)
            stack.append(i)
        
        # 处理遍历完stack还有数据的情况
        while len(stack) > 0:
            cur_height = heights[stack.pop()]
            while len(stack) > 0 and cur_height == heights[stack[-1]]:
                stack.pop()

            if len(stack) > 0:
                cur_width = n - stack[-1] - 1
            else:
                cur_width = n
            res = max(res, cur_height * cur_width)

        return res

复杂度分析

• 时间复杂度，预处理成直方图的时间复杂度为$O(m\ast n)O(m*n)$，而largest_rectangle_area算法对输入数组里的每一个元素入栈一次，出栈一次，时间复杂度是 $O(n)O(n)$ ,所以总的时间复杂度为 $O(m\ast n)+O(n)\ast O(m)=O(m\ast n)O(m*n)\; +\; O(n)*O(m)\; =\; O(m*n)$。
• 空间复杂度，定义了一个heights，所以空间复杂度为$O(m)O(m)$。

点石成金

上述的代码需要考虑两种特殊的情况：

1. 弹出栈顶元素，栈是否为空；
2. 遍历完成以后，栈中还有元素； 而有没有什么办法可以更加优雅地解决？答案是首尾加入都一个0，或者比1小的元素，这两个元素对单调栈不起影响，但可以规避上诉的讨论，我们称之为哨兵。

码上行动

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型
#
class Solution:
    def maximalRectangle(self , matrix: List[List[int]]) -> int:
        # write code here
        # 获取矩阵的长宽
        rows = len(matrix)
        # 如果是空，直接返回
        if rows == 0:
            return 0 
        cols = len(matrix[0])
        heights = [0 for _ in range(cols)]
        res = 0
        # 预处理矩阵
        for i in range(rows):
            for j in range(cols):
                heights[j] = heights[j] + 1 if matrix[i][j] == 1 else 0
                
            res = max(res, self.largest_rectangle_area(heights))
            
        return res
    
    def largest_rectangle_area(self, heights: List[int]) -> int:
        # 判断heights，为空直接返回0
        if len(heights) == 0:
            return 0
        
        res = 0
        n = len(heights)
        # 在首尾分别加入哨兵
        heights = [0] + heights + [0]
        
        # 初始化stack也要加入0
        stack = [0]
        n += 2
        
        # 注意从一开始遍历
        for i in range(1, n):
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]
                cur_width = i - stack[-1] - 1
                res = max(res, cur_height * cur_width)
            stack.append(i)
        return res

复杂度分析

• 时间复杂度，预处理成直方图的时间复杂度为$O(m\ast n)O(m*n)$，而largest_rectangle_area算法对输入数组里的每一个元素入栈一次，出栈一次，时间复杂度是 $O(n)O(n)$ ,所以总的时间复杂度为 $O(m\ast n)+O(n)\ast O(m)=O(m\ast n)O(m*n)\; +\; O(n)*O(m)\; =\; O(m*n)$。
• 空间复杂度，定义了一个heights，所以空间复杂度为$O(m)O(m)$。