求最大子矩阵的大小

[编程题]求最大子矩阵的大小

热度指数：4118 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。

输入描述:

第一行输入两个整数 n 和 m，代表 n*m 的矩阵
接下来输入一个 n*m 的矩阵

输出描述:

输出其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。

示例1

输入

1 4
1 1 1 0

输出

说明

最大的矩形区域有3个1，所以返回3

备注:

算法知识视频讲解

Python

汤普森30

将矩阵变换成直方图，计算直方图中的最大矩形，算法复杂度O(N^2)，不知道是不是因为python的缘故，超时了。。。只能AC75%

N, M= list(map(int,input().split()))
histogram = []
for i in range(N):
    nums = list(map(int,input().split()))
    histogram.append(nums)    #原矩阵
for j in range(M):
    for i in range(1, N):
        if histogram[i][j] == 1:
            histogram[i][j] += histogram[i-1][j]    #构造直方图
# 函数: 计算直方图中的最大矩形
def maxRect(nums):
    stack = []
    maxArea = 0
    nums.append(0)
    for i in range(len(nums)):
        while len(stack)>0 and nums[stack[-1]] > nums[i]:
            H = nums[stack.pop()]
            sidx = -1
            if len(stack)>0:
                sidx = stack[-1]
            area = H * (i-sidx-1)
            maxArea = max(maxArea, area)
        stack.append(i)
    return maxArea
 
maxR = 0
for i in range(N):
    nums = histogram[i]
    maxR = max(maxR, maxRect(nums)) #计算每一行 直方图中的最大矩形   
print(maxR)

编辑于 2019-08-23 19:02:28 回复(0)