Largest Submatrix With Rearrangements
给一个0和1的二维矩阵, 求最大的全1子矩阵(不一定是square).
这个题首先观察例子, 发现肯定有排序, 然后再看一遍能看出来扫描可以通过查找连续1的个数来判断, 所以划分为一个个子问题, 即: 当扫完一行的时候, 如何计算当前的最大全是1的area. 我们需要先找到当前从上到下最多连续1的个数, 然后排序(greedy)后乘以当前的index后取最大.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int largestSubmatrix(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; int[] longest = new int[m]; int res = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 1){ longest[j]++; } else{ longest[j] = 0; } } int[] tmp = Arrays.copyOf(longest, m); Arrays.sort(tmp); for(int j = 0; j < m; j++) { res = Math.max(res, tmp[m - j - 1] * (j + 1)); } } return res; } } |