A39432. 最大矩形面积
填空题
困难
知识点
题目描述
最大矩形面积
题目描述
给出一个n * n（3 ≤ n ≤ 20 ）的二维网格，网格里的数字只有0或1。现在请你计算出只包含1的最大矩形数字和。 （矩形：四个角都是90度的四边形，包含正方形、长方形）。
输入
第一行，一个整数n。
接下来n行，每行n个数，表示n * n的二维网格。
输出
只包含1的最大矩形数字和。
参考答案
# 输入矩阵的大小
n = int(input())
# 输入矩阵元素
matrix = []
for i in range(n):
row = input().split()
matrix.append([int(x) for x in row])
# 计算每个位置向上连续1的数量
heights = [[0]*n for _ in range(n)]
for j in range(n):
for i in range(n):
if matrix[i][j] == 1:
heights[i][j] = (heights[i-1][j] if i > 0 else 0) + 1
# 计算每个位置能够构成的最大矩形面积
max_area = 0
for i in range(n):
stack = []
for j in range(n):
while stack and heights[i][j] < heights[i][stack[-1]]:
height = heights[i][stack.pop()]
width = j if not stack else j - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
stack.append(j)
while stack:
height = heights[i][stack.pop()]
width = n if not stack else n - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
# 输出结果
print(max_area)
上一题
下一题