You are given a binary matrix matrix
of size m x n
, and you are allowed to rearrange the columns of the matrix
in any order.
Return the area of the largest submatrix within matrix
where every element of the submatrix is 1
after reordering the columns optimally.
Example 1:
Input: matrix = [[0,0,1],[1,1,1],[1,0,1]] Output: 4 Explanation: You can rearrange the columns as shown above. The largest submatrix of 1s, in bold, has an area of 4.
Example 2:
Input: matrix = [[1,0,1,0,1]] Output: 3 Explanation: You can rearrange the columns as shown above. The largest submatrix of 1s, in bold, has an area of 3.
Example 3:
Input: matrix = [[1,1,0],[1,0,1]] Output: 2 Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.
Example 4:
Input: matrix = [[0,0],[0,0]] Output: 0 Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j]
is0
or1
.
Solution: DP + Sorting
Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.
[0,0,1] [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1] [2,0,3]
Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order
e.g. i = 2
[0,0,1] [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3] [3,2,0]
row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.
Time complexity: O(m*n*log(n))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int largestSubmatrix(vector<vector<int>>& matrix) { const int m = matrix.size(); const int n = matrix[0].size(); for (int j = 0; j < n; ++j) for (int i = 1; i < m; ++i) if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j]; int ans = 0; for (int i = 0; i < m; ++i) { sort(rbegin(matrix[i]), rend(matrix[i])); for (int j = 0; j < n; ++j) ans = max(ans, (j + 1) * matrix[i][j]); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment