85.md

84 Maximum Rectangle

Description

link

---

Solution

根据84的解法，考虑每一行开始将这题转化为求上一题的结果，用height来表示上一题的height

---

Code

O(n)

class Solution:
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        
        col = len(matrix[0])
        height = [0] * (col+1)
        res = 0
        
        for row in matrix:
            for i in range(col):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            stack = [-1]
            for i in range(col + 1):
                while height[i] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = i - stack[-1] - 1
                    res = max(res,h * w)
                stack.append(i)
        
        return res