###### tags: `Leetcode` `hard` `stack` `python`

# 85. Maximal Rectangle

## [題目連結:]https://leetcode.com/problems/maximal-rectangle/description/

## 題目:
Given a ```rows x cols``` binary ```matrix``` filled with ```0```'s and ```1```'s, find the largest rectangle containing only ```1```'s and return its area.


#### [圖片來源:]https://leetcode.com/problems/maximal-rectangle/description/

## 解題想法:
參考[84. Largest Rectangle in Histogram](/1uv54o3vQFWQj96cLRjIyQ)
* 此題要求求最大矩形面積:
* 只需額外考慮每層的高度即可
* 完全可以使用P84思路
* 有高度，計算寬度即可求面積

matrix = [["1","0","1","0","0"], 第一層
          ["1","0","1","1","1"], 前兩層累加高度
          ["1","1","1","1","1"], 前三層累加高度
          ["1","0","0","1","0"]] 前四層累加高度

想法:
第一層高度為: [1,0,1,0,0]
前二層高度為: [2,0,2,1,1]
前三層高度為: [3,1,3,2,2]
前四層高度為: [4,0,0,3,0]

## Python:

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        #每層都更新res,並累加高度
        if not matrix:
            return 0
        m=len(matrix)
        n=len(matrix[0])
        heights=[0]*n
        res=0
        for row in matrix:
            for j in range(n):
                if row[j]=='1':
                    heights[j]+=1
                else:
                    heights[j]=0
            res=max(res,self.maxArea(heights))
        return res
    #P84程式碼 yyds
    def maxArea(self,heights):
        if not heights:
            return 0
        stack=[]
        Area=0
        heights.append(0)
        for pos in range(len(heights)):
            if not stack or heights[stack[-1]]<heights[pos]:
                stack.append(pos)
            else:
                while stack and heights[stack[-1]]>=heights[pos]:
                    curH=heights[stack[-1]]
                    stack.pop()
                    curW= pos if not stack else pos-stack[-1]-1
                    Area=max(Area,curH*curW)
                stack.append(pos)
        return Area
    
if __name__=='__main__':
    result=Solution()
    ans=result.maximalRectangle(matrix = [["1","0","1","0","0"],
                                          ["1","0","1","1","1"],
                                          ["1","1","1","1","1"],
                                          ["1","0","0","1","0"]])
    print(ans) #6