本文共 2753 字，大约阅读时间需要 9 分钟。
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
思路：
借鉴了leetcode84 的算法，首先对输入的矩阵进行预处理 一开始没有考虑到输入数据的形式是[‘00’,’00’] 以为是[[0,0],[0,0]] 报了很多惨绝人寰的errorT^T情人节不能这样虐我啊 数据处理 [‘01’,’01’]－> [[0,1],[0,2]] 矩阵每一行用leetcode84求直方图最大面积方法求出该行可以达到的最大面积，用max函数保存最大的面积即可
class Solution(object): def maximalRectangle(self,matrix1): matrix=[] maxValue=0 #initial if not len(matrix1): return 0 matrix.append([]) for row in range(len(matrix1[0])): matrix[0].append(int(matrix1[0][row])) for col in range(1,len(matrix1)): matrix.append([]) for row in range(len(matrix1[0])): if not int(matrix1[col][row]): matrix[col].append(0) else: matrix[col].append(int(matrix1[col][row])+int(matrix[col-1][row])) for col in range(len(matrix)): maxValue=max(maxValue,self.largestRectangleArea(matrix[col])) #print matrix return maxValue def largestRectangleArea(self,heights): Stack_Numbers=[] Stack_Index=[] maxS=0 for i in range(len(heights)): if not len(Stack_Numbers): if heights[i]: Stack_Numbers.append(heights[i]) Stack_Index.append(i) else: if heights[i]>=Stack_Numbers[-1]: Stack_Numbers.append(heights[i]) Stack_Index.append(i) else: if heights[i]: for k in range(len(Stack_Numbers)): if Stack_Numbers[k]>heights[i]: temp=Stack_Index[k] for h in range(len(Stack_Numbers)-k): maxS=max(maxS,(i-Stack_Index[k+h])*Stack_Numbers[k+h]) break for h in range(len(Stack_Numbers)-k): Stack_Numbers.pop() Stack_Index.pop() if heights[i]: Stack_Numbers.append(heights[i]) Stack_Index.append(temp) else: for k in range(len(Stack_Numbers)): maxS=max(maxS,(i-Stack_Index[k])*Stack_Numbers[k]) for k in range(len(Stack_Numbers)): Stack_Numbers.pop() Stack_Index.pop() if len(Stack_Numbers): for k in range(len(Stack_Numbers)): maxS=max(maxS,(len(heights)-Stack_Index[k])*Stack_Numbers[k]) return maxS
转载地址：http://hwqmi.baihongyu.com/