Maximum Rectangle

Problem Description
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solutions
I. Solution by finding largest rectangle in histogram

view plainprint?

1. class Solution:  
2.     # @param matrix, a list of lists of 1 length string  
3.     # @return an integer  
4.     def maximalRectangle(self, matrix):  
5.         if not matrix:  
6.             return 0  
7.         h, w = len(matrix), len(matrix[0])  
8.         m = [[0]*w for _ in range(h)]  
9.         for j in range(h):  
10.             for i in range(w):  
11.                 if matrix[j][i] == '1':  
12.                     m[j][i] = m[j-1][i] + 1  
13.         return max(self.largestRectangleArea(row) for row in m)  
14.       
15.     def largestRectangleArea(self, height):  
16.         ''''' 
17.         This uses the way we calculate maximum rectangle in histogram 
18.         '''  
19.         height.append(0)  
20.         stack, area = [], 0  
21.         for i in range(len(height)):  
22.             while stack and height[stack[-1]] > height[i]:  
23.                 h = height[stack.pop()]  
24.                 w = i if not stack else i-stack[-1]-1  
25.                 area = max(area, h*w)  
26.             stack.append(i)  
27.         return area  

class Solution:
    # @param matrix, a list of lists of 1 length string
    # @return an integer
    def maximalRectangle(self, matrix):
        if not matrix:
            return 0
        h, w = len(matrix), len(matrix[0])
        m = [[0]*w for _ in range(h)]
        for j in range(h):
            for i in range(w):
                if matrix[j][i] == '1':
                    m[j][i] = m[j-1][i] + 1
        return max(self.largestRectangleArea(row) for row in m)
    
    def largestRectangleArea(self, height):
        '''
        This uses the way we calculate maximum rectangle in histogram
        '''
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area