Python simple O(mn) solution with detail explanation


  • 1
    L
    class Solution(object):
        def maximalRectangle(self, matrix):
            """
            convert the 2D matrix to one dimensional arr,
            then compute the max rectangle we can get in the one dimensional arr
            :type matrix: List[List[str]]
            :rtype: int
            """
            if not matrix:
                return 0
            m, n = len(matrix), len(matrix[0])
            line = [int(c) for c in matrix[0]]
            res = self.getMaxMaxtrix(line)
            for i in xrange(1, m):
                for j in xrange(n):
                    if matrix[i][j] == '0':
                        line[j] = 0
                    else:
                        line[j] += 1
                res = max(res, self.getMaxMaxtrix(line))
            return res
    
        def getMaxMaxtrix(self, arr):
            """
            compute the max rectangle area in the one dimensional arr
            the basic idea is to check each arr[index], find its left boundary(first left ele which is lower than it)
            find its right boundary,then the area which extend based on index i is:
                area = arr[i]*(right boundary - left boundary -1)
            this can be done in O(n) for each index, so brute force solution is O(n^2)
    
            we can do it in O(n) by leveraging stack to find its boundary.
            walk through the arr from left to right,
            we store index in the stack, and keep the arr[index] with ascending order, therefore, for each element in stack,
            the former ele in stack is its left boundary, when the arr[i] is smaller than arr[stack[-1]],
            we will pop it and compute the maximum rectangle we can construct based on this ele.
            its right boundary is i (because arr[i]<arr[stack[-1]]), left boundary is its former ele in stack.
            so we can compute its area
    
            :param list[int]: the height of the building
            :return: max area
            """
            stack = []
            res = 0
            for i, h in enumerate(arr):
                if i == 0:
                    stack.append(i)
                else:
                    if arr[stack[-1]] <= h:
                        stack.append(i)
                    else:
                        while len(stack) != 0 and arr[stack[-1]] > h:
                            cur_h = arr[stack.pop()]
                            res = max(cur_h * (i - (stack[-1] if len(stack) != 0 else -1) - 1), res)
                        stack.append(i)
            while len(stack) != 0:
                cur_h = arr[stack.pop()]
                res = max(cur_h * (len(arr) - (stack[-1] if len(stack) != 0 else -1) - 1), res)
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.