重新排列后的最大子矩阵

标签: 贪心 数组 矩阵 排序

难度: Medium

给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。

 

示例 1：

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。

示例 2：

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。

示例 3：

输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。

示例 4：

输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。

 

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m * n <= 105
  • matrix[i][j] 要么是 0 ，要么是 1 。

Submission

运行时间: 156 ms

内存: 37.5 MB

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        a = [[0] * n for _ in range(m)]
        r, r1 = matrix[-1], a[-1]
        for i in range(n):
            if r[i]:
                r1[i] = m
        for i in range(m - 2, -1, -1):
            r, r2, k = matrix[i], a[i], i + 1
            r1, r3 = matrix[k], a[k]
            for j in range(n):
                if r[j]:
                    r2[j] = r3[j] if r1[j] else k
        ans = 0
        for i, r in enumerate(a):
            if (m - i) * n <= ans:
                break
            r.sort(reverse=True)
            for j, c in enumerate(r, 1):
                if c == 0:
                    break
                ans = max(ans, j * (c - i))
        return ans

Explain

这个题解的思路是首先计算每个元素在当前列上可达的最大行数，这可以通过从下到上遍历实现。然后对每一行的数列进行排序，并计算可能形成的最大矩形面积，这一步是利用排序后的列值来确定最宽的可能矩形。主要步骤包括：1. 初始化一个与给定矩阵同样大小的矩阵 a，用于记录每个元素上方连续1的数量（包括自身）；2. 从下到上计算矩阵 a 的值；3. 对每一行的列值进行降序排序，并计算每个可能的宽度对应的最大面积。

时间复杂度: O(m * n log n)

空间复杂度: O(m * n)

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        a = [[0] * n for _ in range(m)] # 初始化矩阵 a
        r, r1 = matrix[-1], a[-1]
        for i in range(n):
            if r[i]:
                r1[i] = m # 初始化最底行
        for i in range(m - 2, -1, -1):
            r, r2, k = matrix[i], a[i], i + 1
            r1, r3 = matrix[k], a[k]
            for j in range(n):
                if r[j]:
                    r2[j] = r3[j] if r1[j] else k # 计算上方连续1的数量
        ans = 0
        for i, r in enumerate(a):
            if (m - i) * n <= ans:
                break # 如果当前最大可能面积小于已知答案，中断
            r.sort(reverse=True) # 对每行进行降序排序
            for j, c in enumerate(r, 1):
                if c == 0:
                    break
                ans = max(ans, j * (c - i)) # 计算面积并更新最大值
        return ans

Explore

从下到上遍历使得我们在处理当前行时，下一行（即较低的行）的连续1的数量已经算好，这样可以直接使用这个信息来更新当前行的状态。如果从上到下遍历，因为我们尚未计算下一行的连续1的数量，就无法直接更新当前行，这会使算法更加复杂或者需要更多的状态来记录信息。

这条代码的意思是如果当前行的第 j 列是 1 (`r1[j]`是真)，那么当前元素的上方连续1的数量（不包括当前行）就等于下一行同列元素的上方连续1的数量（`r3[j]`），否则连续性被打断，应重新计数（这里使用`k`，但根据题解的上下文，这似乎是一个错误，理应是设置为0）。这种方式确保了只有在当前列元素为1且上一行同列也是1的情况下，连续性才被保持。

降序排序是为了使每行的列值按从大到小排列，这样在计算每个可能的宽度对应的最大矩形面积时，可以直接取用最大的连续1的数量。如果使用升序，我们需要从列表的末尾开始计算，这在逻辑上更复杂且不直观。通过降序，我们可以保证在宽度为 j 时，所使用的行高都是当前可能的最大值，从而最大化矩形的面积。

这个条件是基于面积的最大可能估计来设置的。`(m - i) * n`表示从当前行到矩阵底部的所有行构成的最大可能矩形区域的面积（假设全部是1）。如果这个值已经小于或等于当前已知的最大矩形面积`ans`，那么即使在之后的行中找到了更大的连续1的数量，也无法构成更大的矩形面积，所以可以提前终止循环，节省计算资源。