題目描述：

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

示例:

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

Solution：

參考了題解的一種方法：

動態規劃 - 每個點的最大高度

想象一個算法，對于每個點我們會通過以下步驟計算一個矩形：

不斷向上方遍歷，直到遇到“0”，以此找到矩形的最大高度。

向左右兩邊擴展，直到無法容納矩形最大高度。

我們知道，最大矩形必為用這種方式構建的矩形之一。

給定一個最大矩形，其高為 h， 左邊界 l，右邊界 r，在矩形的底邊，區間 [l, r]內必然存在一點，其上連續1的個數（高度）<=h。若該點存在，則由于邊界內的高度必能容納h，以上述方法定義的矩形會向上延伸到高度h，再左右擴展到邊界 [l, r] ，于是該矩形就是最大矩形。

若不存在這樣的點，則由于[l, r]內所有的高度均大于h，可以通過延伸高度來生成更大的矩形，因此該矩形不可能最大。

綜上，對于每個點，只需要計算h， l，和 r - 矩形的高，左邊界和右邊界。

使用動態規劃，我們可以在線性時間內用上一行每個點的 h，l，和 r 計算出下一行每個點的的h，l，和r。

算法

給定一行 matrix[i]，我們通過定義三個數組height，left，和 right來記錄每個點的h，l，和 r。height[j] 對應matrix[i][j]的高，以此類推。

問題轉化為如何更新每個數組。

Height:

這個比較容易。 h 的定義是從該點出發連續的1的個數。我們從方法二中已經學會了在一行中計算的方法:

row[j] = row[j - 1] + 1 if row[j] == '1'

只需要一點改動即可:

new_height[j] = old_height[j] + 1 if row[j] == '1' else 0

Left:

考慮哪些因素會導致矩形左邊界的改變。由于當前行之上的全部0已經考慮在當前版本的left中，唯一能影響left就是在當前行遇到0。

因此我們可以定義:

new_left[j] = max(old_left[j], cur_left)

cur_left是我們遇到的最右邊的0的序號加1。當我們將矩形向左 “擴展” ，我們知道，不能超過該點，否則會遇到0。

Right:

我們可以沿用 left 的思路，定義:

new_right[j] = min(old_right[j], cur_right)

cur_right 是我們遇到的最左邊的0的序號。簡便起見，我們不把 cur_right 減去1 (就像我們給cur_left加上1那樣) ，這樣我們就可以用height[j] * (right[j] - left[j]) 而非height[j] * (right[j] + 1 - left[j])來計算矩形面積。

這意味著， 嚴格地說 ，矩形的底邊由半開半閉區間[l, r) 決定，而非閉區間 [l, r]，且 right比右邊界大1。盡管不這樣做算法也可以正確運行，但這樣會讓計算看起來更簡潔。

注意，為了正確的記錄 cur_right，我們需要從右向左迭代。因此，更新right時需要從右向左。

一旦left，right，和 height數組能夠正確更新，我們就只需要計算每個矩形的面積。

由于我們知道矩形 j的邊界和高，可以簡單地用height[j] * (right[j] - left[j])來計算面積，若j的面積 大于max_area，則更新之。

CODE:

            
              class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:return 0
        m,n = len(matrix),len(matrix[0])
        left = [0]*n
        right = [n]*n
        height = [0]*n
        maxArea = 0
        for i in range(m):
            curleft = 0
            curright = n
            for j in range(n):
                if matrix[i][j] == '1':
                    height[j] = height[j]+1
                else:height[j] = 0
            for j in range(n):
                if matrix[i][j] == '1':
                    left[j] = max(left[j],curleft)
                else:
                    left[j] = 0
                    curleft = j + 1
            for j in range(n-1,-1,-1):
                if matrix[i][j] == '1':
                    right[j] = min(right[j],curright)
                else:
                    right[j] = n
                    curright = j
            for j in range(n):
                maxArea = max(maxArea,height[j]*(right[j]-left[j]))
        return maxArea
            
        
        
        
            
          

復雜度分析*

??? 時間復雜度 : O(NM)。每次對于N的迭代我們會對M迭代常數次。

??? 空間復雜度 : O(M）， M 是我們保留的額外數組的長度。