算法随笔_44: 最大矩形
上一篇:算法随笔_43: 柱状图中最大的矩形_单调栈-CSDN博客
=====
题目描述如下:
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。
=====
算法思路:
这道题看似困难，其实如果了解了上一篇的算法原理的话，这道题就不是很难了。
这道题需要求出最大矩形，这很像上一道题。如果我们把每一列看成一个柱子，那就和上一道题一样了。
我们把矩阵的一行想象成柱形图的底部，每一列做为柱形图的柱子。从底部开始连续出现的1的次数为柱子的高。我们可以对这样生成的柱状图求出其最大矩形p_area_max。这样，我们就可以利用上一篇的算法来求出p_area_max。
由于题解的最大矩形必然出现在以每行为底的柱状图中，因此我们可以对每行的柱状图求出其p_area_max。然后取最大值就是最终答案。
算法总体思路已经有了，接下来我们看一些细节问题。我们需要统计出以每行为底的柱状图。这也是一个二维数组，我们设它为hghs，其行列大小和matrix一样。
现在，我们从上往下看这个矩形matrix。
第一行matrix[0]的所有数值就是以它为底的柱状图的高度。我们把它存入hghs。
第二行，如果当前格matrix[1][j]为1，那么hghs[1][j]的高度应该等于hghs[0][j]的高度加1。如果当前格matrix[1][j]为0，那么hghs[1][j]的高度应该等于0。
后面的行以此类推，我们可以统计出所有的行的柱状图。
算法的时间复杂度:
m，n分别为原矩形的行数和列数。统计hghs的时间复杂度为O(m*n) 。求出每行的最大矩形为O(n) 。求出所有行的最大矩形为O(m*n) 。所以最终的算法时间复杂度为O(m*n) 。
下面是代码实现:
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
h_len=len(heights)
w_r=[0]*h_len
w_l=[0]*h_len
stck=[]
for i in range(h_len):
while len(stck)>0 and heights[i]<=heights[stck[-1]]:
stck.pop()
w_l[i]=stck[-1]+1 if len(stck)>0 else 0
stck.append(i)
stck=[]
for i in range(h_len-1,-1,-1):
while len(stck)>0 and heights[i]<=heights[stck[-1]]:
stck.pop()
w_r[i]=stck[-1]-1 if len(stck)>0 else h_len-1
stck.append(i)
res=0
for i in range(h_len):
area=heights[i]*(w_r[i]-w_l[i]+1)
res=max(res,area)
return res
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
row_n=len(matrix)
col_n=len(matrix[0])
res=0
hghs = [[0 for _ in range(col_n)] for _ in range(row_n)]
for i in range(row_n):
for j in range(col_n):
if matrix[i][j]=="1":
if i>0:
hghs[i][j]=hghs[i-1][j]+1
else:
hghs[i][j]=1
for i in range(row_n):
tmp=self.largestRectangleArea(hghs[i])
res=max(tmp,res)
return res