# LeetCode 85 Maximal Rectangle (Python详解及实现)

【题目】

Given a 2D binary matrix filled with 0'sand 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 6.

【思路】

【Python实现】

# -*- coding: utf-8 -*-

"""

Created on Wed Aug  9 15:34:39 2017

"""

class Solution(object):

def maximalRectangle(self, matrix):

"""

:type matrix: List[List[str]]

:rtype: int

"""

if  matrix == [] or len(matrix) ==0:

return 0

maxArea = 0

heights = [0 for i in range(len(matrix[0]))]

for i in range(len(matrix)):

for j in range(len(matrix[i])):

heights[j] = heights[j] + 1 ifmatrix[i][j] == '1' else 0 #计算高度值

maxArea = max(maxArea,self.largestRectangleArea(heights))

print(maxArea)

return maxArea

def largestRectangleArea(self, heights):

maxArea = 0

stack = []

i = 0

while i < len(heights):

if len(stack) == 0 or stack[-1] <= heights[i]:

stack.append(heights[i])

else:

count = 0

while len(stack) > 0 andstack[-1] > heights[i]:#height[i]小于栈顶元素

count += 1

maxArea = max(maxArea,int(stack[-1])*count)

stack.pop()#栈顶元素出栈

while count > 0:#将当前height入栈

count -= 1

stack.append(heights[i])

stack.append(heights[i])

i += 1

count = 1

while len(stack) != 0:

maxArea = max(maxArea, int(stack[-1])*count)

stack.pop()

count += 1

return maxArea

if __name__ == '__main__':

S= Solution()

heights =["10100","10111","11111","10010"]

maxarea = S.maximalRectangle(heights)