题目描述
给定一个二进制矩阵 matrix
,它的大小为 m x n
,你可以将 matrix
中的 列 按任意顺序重新排列。
请你返回最优方案下将 matrix
重新排列后,全是 1
的子矩阵面积。
样例
输入:matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出:4
解释:你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分,面积为 4。
输入:matrix = [[1,0,1,0,1]]
输出:3
解释:你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分,面积为 3。
输入:matrix = [[1,1,0],[1,0,1]]
输出:2
解释:由于你只能整列整列重新排布,所以没有比面积为 2 更大的全 1 子矩形。
输入:matrix = [[0,0],[0,0]]
输出:0
解释:由于矩阵中没有 1 ,没有任何全 1 的子矩阵,所以面积为 0。
限制
m == matrix.length
n == matrix[i].length
1 <= m * n <= 10^5
matrix[i][j]
要么是0
,要么是1
。
算法
(排序) $O(m n \log n)$
- 枚举每一行当做矩形的底。
- 对于在当前行的每一列,计算出其往上的连续的 1 的个数。这个信息可以通过上一行继承,避免重复计算。
- 将计算结果从大到小排序,然后计算出当前行最大的矩形面积,更新答案。
时间复杂度
- 共有 $m$ 行,每一行下计算的的时间复杂度为 $O(n \log n)$。
- 故总时间复杂度为 $O(m n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储每一列往上的连续的 1 的个数。
C++ 代码
class Solution {
public:
int largestSubmatrix(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> heights(n, 0);
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) heights[j] = 0;
else heights[j]++;
vector<int> h(heights);
sort(h.begin(), h.end());
for (int i = h.size() - 1; i >= 0; i--)
if (ans < h[i] * (h.size() - i))
ans = h[i] * (h.size() - i);
}
return ans;
}
};