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) line = [int(c) for c in matrix] 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
Python simple O(mn) solution with detail explanation
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.