Leetcode 85. Maximal Rectangle

Seawolf

1. Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
   
2. 
   
3. Example:
   
4. 
   
5. Input:
   
6. [
   
7.   ["1","0","1","0","0"],
   
8.   ["1","0","1","1","1"],
   
9.   ["1","1","1","1","1"],
   
10.   ["1","0","0","1","0"]
    
11. ]
    
12. Output: 6

复制代码

1. class Solution:
   
2.     def maximalRectangle(self, matrix: List[List[str]]) -> int:
   
3.         if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
   
4.             return 0
   
5.         m = len(matrix)
   
6.         n = len(matrix[0])
   
7.         height = [0] * n
   
8.         res = 0
   
9.         for row in matrix:
   
10.             for i in range(n):
    
11.                 height[i] = height[i] + 1 if row[i] == '1' else 0
    
12.             stack = []
    
13.             for i in range(n + 1):
    
14.                 if i == n:
    
15.                     curt = -1
    
16.                 else:
    
17.                     curt = height[i]
    
18.                 while stack and curt <= height[stack[-1]]:
    
19.                     h = height[stack.pop()]
    
20.                     if len(stack) == 0:
    
21.                         w = i
    
22.                     else:
    
23.                         w = i - stack[-1] - 1
    
24.                     res = max(res, h * w)
    
25.                 stack.append(i)
    
26.         return res

复制代码