[leetcode]@python 85. Maximal Rectangle

题目链接

https://leetcode.com/problems/maximal-rectangle/

题目原文

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

题目大意

给出一个包含0和1的矩阵，在矩阵中找到一个矩形，这个矩形只包含1

解题思路

道题需要利用上一道题（Largest Rectangle in Histogram）的结论。比如对于以下矩阵。
0 0 0 0
0 0 1 0
0 1 1 0
1 0 1 1
对于这个矩阵，对于每一行，我们按照上一道题的算法求解一遍，最后得出的就是最大的矩阵。

代码

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = []
        i = 0
        area = 0

        while i < len(heights):
            if stack == [] or heights[i] > heights[stack[len(stack) - 1]]:
                stack.append(i)
            else:
                cur = stack.pop()
                if stack == []:
                    width = i
                else:
                    width = i - stack[len(stack) - 1] - 1
                area = max(area, width * heights[cur])
                i -= 1
            i += 1

        while stack != []:
            cur = stack.pop()
            if stack == []:
                width = i
            else:
                width = len(heights) - stack[len(stack) - 1] - 1
            area = max(area, width * heights[cur])

        return area

    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if matrix == []:
            return 0
        a = [0 for i in range(len(matrix[0]))]
        maxArea = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == '1':
                    a[j] = a[j] + 1
                else:
                    a[j] = 0
            maxArea = max(maxArea, self.largestRectangleArea(a))
        return maxArea