rearrange二维矩阵的列,问能构成的最大的全1子矩阵有多大,贪心,先按列求每一行的prefix sum(因为行顺序不能换,所以遇到0的话要清0),然后遍历每一行,更新最大子矩阵尺寸
1 #1727
2 #Runtime: 1041 ms (Beats 11.18%)
3 #Memory: 44.8 MB (Beats 45.71%)
4
5 class Solution(object):
6 def largestSubmatrix(self, matrix):
7 """
8 :type matrix: List[List[int]]
9 :rtype: int
10 """
11 r, c = len(matrix), len(matrix[0])
12 ans = 0
13 for i in xrange(1, r):
14 for j in xrange(c):
15 matrix[i][j] += matrix[i - 1][j] if matrix[i][j] else 0
16 for i in xrange(r):
17 matrix[i].sort(reverse=True)
18 for j in xrange(c):
19 ans = max(ans, (j + 1) * matrix[i][j])
20 return ans