[已解决]求最大矩形

Stubborn

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

来源：力扣（LeetCode）链接：

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2019-11-20 12:15:16

仅包含 0 和 1 的

乱码咯，编辑一下吧，虽然能看懂……

解答：

1. def solve(give)->int:
   
2.     area = 0
   
3.     a,b=0,0
   
4.     height = len(give)
   
5.     width = len(give[0])
   
6.     for i in range(height):
   
7.         bottom = height
   
8.         for j in range(width):
   
9.             if give[i][j] == '1':
   
10.                 a += 1
    
11.             else:
    
12.                 a,b = 0,0
    
13.             for q in range(i,bottom):
    
14.                 if give[q][j] == '1':
    
15.                     b += 1
    
16.                     area = max(area,a*b)
    
17.                     #print('调试\n\ti\tj\tq\ta\tb\tmul\tarea\n',i,j,q,a,b,a*b,area,sep='\t')
    
18.                     if q == bottom-1:
    
19.                         b = 0
    
20.                         if not i:
    
21.                             if area == height*width:
    
22.                                 return area
    
23.                 else:
    
24.                     bottom = q
    
25.                     b = 0
    
26.             if j == width-1:
    
27.                 a,b = 0,0
    
28.     return area
    
29. 
    
30. if __name__ == '__main__':
    
31.     matrix = [
    
32.   ["1","0","1","0","0"],
    
33.   ["1","0","1","1","1"],
    
34.   ["1","1","1","1","1"],
    
35.   ["1","0","0","1","0"]
    
36. ]
    
37.     print('6 输出',solve(matrix))
    
38.     test = [
    
39. ['1','1'],
    
40. ['1','1']
    
41. ]
    
42.     print('4 输出',solve(test))
    

复制代码

时间复杂度:O(height*width*height!)
不晓得能不能再优化

跳转到最佳答案楼层

阴阳神万物主

仅包含 0 和 1 的

乱码咯，编辑一下吧，虽然能看懂……

解答：

1. def solve(give)->int:
   
2.     area = 0
   
3.     a,b=0,0
   
4.     height = len(give)
   
5.     width = len(give[0])
   
6.     for i in range(height):
   
7.         bottom = height
   
8.         for j in range(width):
   
9.             if give[i][j] == '1':
   
10.                 a += 1
    
11.             else:
    
12.                 a,b = 0,0
    
13.             for q in range(i,bottom):
    
14.                 if give[q][j] == '1':
    
15.                     b += 1
    
16.                     area = max(area,a*b)
    
17.                     #print('调试\n\ti\tj\tq\ta\tb\tmul\tarea\n',i,j,q,a,b,a*b,area,sep='\t')
    
18.                     if q == bottom-1:
    
19.                         b = 0
    
20.                         if not i:
    
21.                             if area == height*width:
    
22.                                 return area
    
23.                 else:
    
24.                     bottom = q
    
25.                     b = 0
    
26.             if j == width-1:
    
27.                 a,b = 0,0
    
28.     return area
    
29. 
    
30. if __name__ == '__main__':
    
31.     matrix = [
    
32.   ["1","0","1","0","0"],
    
33.   ["1","0","1","1","1"],
    
34.   ["1","1","1","1","1"],
    
35.   ["1","0","0","1","0"]
    
36. ]
    
37.     print('6 输出',solve(matrix))
    
38.     test = [
    
39. ['1','1'],
    
40. ['1','1']
    
41. ]
    
42.     print('4 输出',solve(test))
    

复制代码

时间复杂度:O(height*width*height!)
不晓得能不能再优化