Question: https://oj.leetcode.com/problems/maximal-rectangle/
Question Name: Maximal Rectangle
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): stack = [] # Store the position of bars with non-decreasing height maxArea = 0 height.append(-1) # Append a pseudo bar at the end so that, after # the while loop, the one and the only on bar # left in the stack will definitely be this # pseudo bar. index = 0 # In this loop, we are using the stack to find out the largest zone # for each bar (to say i), in which bar i is the shortest one. while index < len(height): if len(stack) == 0: # This is the first bar. OR all of its previous bars are # higher than this one. stack.append(index) index += 1 elif height[index] >= height[stack[-1]]: stack.append(index) index += 1 else: preBasin = stack.pop() if len(stack) == 0: # From beginning to index-1 position, the preBasin has # the shortest bar. maxArea = max(maxArea, height[preBasin] * index) else: # From stack[-1] position to index-1 position, the # preBasin has the shortest bar. maxArea = max(maxArea, height[preBasin] * (index-stack[-1]-1) ) return maxArea # @param matrix, a list of lists of 1 length string # @return an integer def maximalRectangle(self, matrix): # Handle the special case that the matrix is empty if len(matrix) == 0: return 0 # heights[i][j] means on the i(th) row, begin with j(th) position, # how many consecutive one(s) are there. heights = [[0] * len(matrix[0]) for _ in xrange(len(matrix))] for row in xrange(len(matrix)): # We are going to travel the row from the end to the beginning if matrix[row][-1] == "1": heights[row][-1] = 1 for col in xrange(len(matrix[0])-2, -1, -1): if matrix[row][col] == "0": heights[row][col] = 0 else: heights[row][col] = heights[row][col+1] + 1 # We transfer the original challenge into an old question: Largest # Rectangle in Histogram. We compute the largest rectangle on each # column (towards right). And then choose the maximum among them. maxArea = 0 for x in xrange(len(matrix[0])): maxArea = max(maxArea, self.largestRectangleArea( [heights[y][x] for y in xrange(len(matrix))])) return maxArea |