Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理