85. Maximal Rectangle 最大矩形

首先是延续上一题的84题中的思路

class Solution:
   def maximalRectangle(self, matrix: List[List[str]]) -> int:
       row = len(matrix)
       if row == 0:
           return 0
       column = len(matrix[0])
       result = 0
       heights = [0]*column
       for i in range(row):
           for j in range(column):
               heights[j] = heights[j]+1 if matrix[i][j]=='1' else 0
           result = max(result, self.largestRectangleArea(heights))
       return result
   
   
   def largestRectangleArea(self, heights: List[int]) -> int:
       length = len(heights)
       if length == 0:
           return 0
       if length == 1:
           return heights[0]
       heights.append(0)
       result = 0
       stack = []
       for i in range(length+1):
           while len(stack) > 0 and heights[stack[-1]] >= heights[i]:
               cur = stack[-1]
               stack.pop()
               if len(stack)>0:
                   # 注意此处的stack栈顶元素已经变化
                   # print('cur,i,stack',cur,i,stack)
                   area = heights[cur] * (i-stack[-1]-1) 
               else:
                   # 此时说明？
                   area = heights[cur]*i
               # print(area)
               result = max(result, area)
           stack.append(i)
           # print("stack",stack)

       return result