重新排列后的最大子矩阵
难度:
标签:
题目描述
给你一个二进制矩阵 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.lengthn == matrix[i].length1 <= m * n <= 105matrix[i][j]要么是0，要么是1。
代码结果
运行时间: 156 ms, 内存: 37.5 MB
/*
* 使用Java Stream的方式解决问题：
* 1. 计算每一列的高度。
* 2. 对每一行排序后计算面积。
* 3. 使用Stream API实现数组的处理。
*/
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public int largestSubmatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int maxArea = 0;
// 计算每一列的高度
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] += matrix[i - 1][j];
}
}
}
// 对每一行进行排序并计算面积
for (int i = 0; i < m; i++) {
int[] sortedRow = Arrays.stream(matrix[i])
.boxed()
.sorted(Comparator.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, sortedRow[j] * (j + 1));
}
}
return maxArea;
}
}解释
方法:
这个题解的思路是首先计算每个元素在当前列上可达的最大行数，这可以通过从下到上遍历实现。然后对每一行的数列进行排序，并计算可能形成的最大矩形面积，这一步是利用排序后的列值来确定最宽的可能矩形。主要步骤包括：1. 初始化一个与给定矩阵同样大小的矩阵 a，用于记录每个元素上方连续1的数量（包括自身）；2. 从下到上计算矩阵 a 的值；3. 对每一行的列值进行降序排序，并计算每个可能的宽度对应的最大面积。
时间复杂度:
O(m * n log n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
在计算每个元素上方连续1的数量时，为什么要从下到上遍历，而不是从上到下遍历？
▷🦆
如何理解题解中的操作`r2[j] = r3[j] if r1[j] else k`？这里的逻辑是如何确保连续性的？
▷🦆
在处理矩阵a之后进行的降序排序，为什么选择降序而不是升序？这对最终计算的面积有何影响？
▷🦆
题解中提到的条件`(m - i) * n <= ans`用于中断循环，这个判断条件是如何得出的？它是基于什么逻辑或数学推导？
▷