力扣鏈接:85. 最大矩形 - 力扣（LeetCode）
給定一個僅包含?0?和?1?、大小為?rows x cols?的二維二進制矩陣，找出只包含?1?的最大矩形，并返回其面積。
輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 輸出：6 解釋：最大矩形如上圖所示。
輸入：matrix = [["0"]] 輸出：0
輸入：matrix = [["1"]] 輸出：1
"""
思路:
此題和84題思路一樣,只是增加的條件,我們可以把他看成多層疊加的
我們可以把二維數組轉換成1維的高度數組
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]
]
我們可以看成4個一維的高度數組,高度就是當前行的位置1增加,如果當前行的位置為0則高度就是0第1行為底的柱子:["1","0","1","0","0"] max = 1
第2行為底的柱子:["2","0","2","1","1"] max = 3
第3行為底的柱子:["3","1","3","2","2"] max = 6
第4行為底的柱子:["4","0","0","3","0"] max = 4"""
from platform import mac_verdef maximalRectangle(matrix):m = len(matrix)n = len(matrix[0])heights_list = []heights = [0] * n# 遍歷每一行for i in range(m):for j in range(n):# 如果當前位置是 '1'，則增加高度，否則高度為 0if matrix[i][j] == '1':heights[j] = heights[j] + 1else:heights[j] = 0# heights_list.append(heights[:]) # 此處有坑,heights[:]等于copy,不然append的都是最后一個 heightsheights_list.append(heights.copy())# 這里就可以調用84題的方法來處理def largestRectangleArea(heights):max_area = 0 # 記錄最大值for i in range(len(heights)): # 循環遍歷每一個索引位置p = i # 初始p為當前的i的位置while p < len(heights): # p到達數組末尾,結束循環if heights[p] == 0: # 當p位置的值是0的時候,直接跳出循環,因為0高度,不能構成矩形breakw = p - i + 1 # 計算當前p位置到i位置的寬度cur_value = w * min(heights[i:p + 1]) # 高取當前i和p位置數組中的最小的值,矩形面積是有最矮的構成的來決定的max_area = max(max_area, cur_value) # 更新最大面積的值p = p + 1 # 指針右移動return max_areamax_area = 0for heights in heights_list:value = largestRectangleArea(heights)max_area = max(max_area, value)return max_areaprint(maximalRectangle([["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]))
print(maximalRectangle([["1"]]))
print(maximalRectangle([["0"]]))
)
