題目鏈接
難度：困難 ??????類型：動(dòng)態(tài)規(guī)劃

給定一個(gè)僅包含 0 和 1 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形，并返回其面積。

示例

輸入:
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
輸出: 6

解題思路

矩形的面積等于，分別找出和即可

1. 計(jì)算
   row[i]是matrix的第i行，每行有n列，例如示例中，n=5
   到達(dá)第行時(shí)
   當(dāng)row[i][j] == '0' 時(shí)(其中)，
   當(dāng)row[i][j] == '1' 時(shí)(其中)，
   例如，i = 2時(shí)，h = [3, 1, 3, 2, 2]，每一行都要求出h，一共求4組
2. 找到
   對(duì)于第2行的h，[3, 1, 3, 2, 2]，前三行所構(gòu)成的矩形的面積可以是1，2，3，4，6，這是因?yàn)槿チ瞬煌?img class="math-inline" src="https://math.jianshu.com/math?formula=w" alt="w" mathimg="1">所造成的
   當(dāng)是，面積等于6
   [["x","x","x","x","x"],
   ["x","x","1","1","1"],
   ["x","x","1","1","1"],
   ["x","x","x","x","x"]
   當(dāng)是，面積等于5
   [["x","x","x","x","x"],
   ["x","x","x","x","x"],
   ["1","1","1","1","1"],
   ["x","x","x","x","x"]
   找出所有的和的組合，像極了84題：柱狀圖中最大的矩形

代碼實(shí)現(xiàn)

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        height = [0] * (n+1)
        max_area = 0
        for row in matrix:
            # 計(jì)算h
            for i in range(n):
                height[i] = height[i]+1 if row[i]=='1' else 0
            # 找出所有h和w的組合 
            stack = [-1]
            for j in range(n + 1):
                while height[j] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = j - 1 - stack[-1]
                    max_area = max(max_area, h * w)                
                stack.append(j)            
        return max_area

本文鏈接：http://www.itdecent.cn/p/67cd5ba8802c