Python - 寻找最大矩形 数字版&矩阵版

Python - 寻找最大矩形 数字版&矩阵版 一.引言

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

 例如给定如上 4 x 5 的 0-1 矩阵，由1组成的最大矩形面积为6。

二.寻找最大矩形-数字版

引言中的题目为寻找最大矩形的矩阵版本，在解答矩阵版本之前，先通过数字版本了解解题流程，再看下面的矩阵版本解答就会清晰很多。

1.题目要求

给定n个表示直方图条高的非负整数，其中每个条的宽度为1，求直方图中最大矩形的面积。

2.实现思路

当前数组 [2, 1 ,5, 6, 2, 3] ，可以先采用数形结合的思想看一下：

(1) 针对每一个点，其对应位置的高度为其数组中对应索引的值

(2) 针对每一个点，以该点为起点构造矩形，需要其左右位置的点连续且高度均小于等于自己

(3) 分别向左，向右延伸，寻找高度大于等于自己的点，直到条件不满足退出，此时满足的位置数 + 1[自身] 即为矩形的长 width，对应索引的值即为矩形的高 height，width x height 即为当前点的最大矩形面积

(4) 初始化 max = 0，遍历所有点，更新最大值并返回

Tips:

以位置1为起点构造矩形，左边没有元素，右边元素值小于等于2，结束，此时面积 = 1 x 2 = 2

以位置2为起点构造矩形，左边1个元素满足，右边4个元素满足，结束，此时面积 = 1 x (1+1+4) = 6

  ......

依次类推，最终得到最大的面积为位置2 与 位置3 重叠的区域，其最大面积为10 :

3.实现代码

实现非常简单，向左向右判断两个 if-else 即可，如果觉得 range 逻辑不太清晰，也可以使用 while-true ，更方便理解

#!/usr/bin/python
# -*- coding: UTF-8 -*-
nums = [2, 1, 5, 6, 2, 3]


def findMaxRectangle(nums):
    row = len(nums)
    _max = 0
    for i in range(row):
        cur_height = nums[i]  # 获取当前 height
        cur_width = 1  # 初始化当前 width
        # 向左寻找
        for j in range(i - 1, -1, -1):
            if nums[j] >= cur_height:
                cur_width += 1
            else:
                break
        # 向右寻找
        for k in range(i + 1, row, 1):
            if nums[k] >= cur_height:
                cur_width += 1
            else:
                break
        # area = width * height
        now_max = cur_width * cur_height
        _max = max(_max, now_max)
    print(_max)
    return _max


maxArea = findMaxRectangle(nums)
print("最大面积为: %d" % maxArea)

三.寻找最大矩形-矩阵版 1.题目要求

矩阵版本题目这里再重复一下 : 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

2.实现思路 

矩阵版的求最大矩形可以拆解为 row 个寻找最大矩形数字版，针对每一行，我们都可以将当前行作为一个数组 nums，每一个点的高度看做其向上数字连续为1的数量，下面图例看一下:

针对第一行:

当前对应的 nums = [1,0,1,0,0] ，此时最大矩形面积为1

...... 

针对第三行:

当前 nums = [3, 1, 3, 2, 2] 通过上面的 findMaxRectangle 方法对该 nums 遍历寻找最大面积即可

根据上面的解析步骤也就清晰了：

(1) 针对每行，遍历每列，寻找其上面连续为 1 的格点作为该点的 height，完成行 -> nums 的映射

(2) 针对每行生成的 nums ，使用 findMaxRectangle 方法获取其最大面积 max

(3) 将各行的 max 比较，获得最大面积

3.实现代码

nums2 = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]


def getHeightList(matrix):
    _max = 0
    print("================")
    for i in nums2:
        print(i)
    print("================")
    # 退出条件
    if matrix is None or len(matrix) == 0:
        return 0
    # 获取矩阵的长，宽
    row = len(matrix)
    col = len(matrix[0])
    cur_height = [0] * col
    # 累加获取每行对应的 nums 数组
    for i in range(row):
        for j in range(col):
            if (matrix[i][j]) == 1:
                cur_height[j] += 1
            else:
                cur_height[j] = 0
        # 为每行 nums 数组计算本行的最大矩阵面积
        cur_max = findMaxRectangle(cur_height)
        _max = max(cur_max, _max)
    print("================")
    return _max


maxArea = getHeightList(nums2)
print("最大面积为: %d" % maxArea)

可以看到每行对应的面积分别为1,3,6,4，最终取最大6代表当前0-1矩阵可以找出的最大矩形面积

================
[1, 0, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 0, 0, 1, 0]
================
1
3
6
4
================
最大面积为: 6

四.算法分析

最大矩数字版是矩阵版的子集，所以这里只分析矩阵版:

(1) 根据每行数据构造 height nums 数组

时间复杂度: O(n^2)   |  矩阵完整遍历

空间复杂度: O(n)  | 需要一个长度为 row 的数组保存当前 height

(2) 根据数组寻找最大矩形面积 findMaxRectangle

时间复杂度: 遍历行 (n) x 遍历列 (1-n) = O(n) - O(n^2) 

遍历列时可能一步不走，也可能遍历全部 col，所以复杂度为 0-n

空间复杂度: 

只需要两个临时变量 cur_height ，cur_width 和 _max 变量，基本忽略

(3) 对称性

对于矩阵而言，其形状为 row x col，转置后的矩阵 col x row 在计算最大矩阵面积时二者结果相同，同等条件下调整 row ,col 可以获得更优的速度，下面验证一下:

row = 1000
col = 10
randomMatrix = np.random.randint(0, 2, size=(row, col))
time1 = time.time()
maxArea = getHeightList(randomMatrix)
print("最大面积为: %d" % maxArea)
time2 = time.time()
transpose = np.transpose(randomMatrix)
time3 = time.time()
maxArea = getHeightList(transpose)
print("最大面积为: %d" % maxArea)
time4 = time.time()
print("%d x %d Cost: %s" % (row, col, (time2 - time1)))
print("%d x %d Cost: %s" % (col, row, (time4 - time3)))

1000 x 10 Cost: 0.010404109954833984
10 x 1000 Cost: 0.2546980381011963

可以看到，当 row >> col 的时候，相同矩阵相同算法得到相同答案的速度可以相差几十倍。