刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

题目描述：

（注.input（）输入函数的括号中不允许添加任何信息）

时间限制：3000MS 内存限制：589824KB

编程实现：

小明有一张N*M的方格纸，且部分小方格中涂了颜色，部分小方格还是空白。

给出N（2≤N≤30）和M（2≤M≤30）的值，及每个小方格的状态（被涂了颜色小方格用数字1表示，空白小方格用数字0表示），请帮助小明找出最大的矩形空白区域，并输出该矩形空白区域由多少个小方格组成。

例如：N=4，M=5，4*5的方格纸中每个小方格的状态如下图：

最大的空白区域由6个小方格组成（红色框区域）。

输入描述

第一行输入两个正整数N和M（2≤N≤30，2≤M≤30），分别表示方格纸的行数和列数，两个正整数之间以一个空格隔开

第二行开始输入N行，每行M个整数（整数为1或者0），1表示涂色方格，0表示空白方格，整数之间以一个空格隔开

输出描述

输出一个整数，表示最大矩形由多少个小方格组成（如果没有空白小方格，输出0）

样例输入

4 5
1 1 0 0 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 0

样例输出

6

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef max_rectangle(matrix):if not matrix:return 0rows, cols = len(matrix), len(matrix[0])heights = [0] * colsmax_area = 0for i in range(rows):for j in range(cols):if matrix[i][j] == 0:heights[j] += 1else:heights[j] = 0max_rect_area = max(max_rect_area,calculate_rectangle_area(heights, i))return max_rect_areadef calculate_rectangle_area(heights, row):stack = []max_area = 0for j in range(len(heights)):while stack and heights[j] < heights[stack[-1]]:width = j - stack.pop()max_area = max(max_area,heights[stack[-1]] * width)stack.append(j)while stack:width = len(heights) - stack.pop()max_area = max(max_area,heights[stack[-1]] * width)return max_areaN, M = map(int, input().split())matrix = [list(map(int, input().split())) for _ in range(N)]print(max_rectangle(matrix))```

解析：

【喵呜刷题小喵解析】：

本题要求找出给定方格纸中最大的空白矩形区域，并输出该区域的小方格数量。

首先，我们可以使用单调栈来解决这个问题。对于每一行，我们计算每个位置左侧连续0的个数，即高度。然后，我们可以使用单调栈来找到以当前行为底的最大矩形面积。

具体步骤如下：

1. 创建一个与方格纸列数相同长度的列表`heights`，用于存储每个位置左侧连续0的个数。
2. 遍历方格纸的每一行，对于每个位置，如果方格是0，则`heights`中对应位置的值加1，否则重置为0。
3. 对于每一行，使用单调栈计算以当前行为底的最大矩形面积。
4. 遍历`heights`列表，如果栈不为空且当前高度小于栈顶高度，则计算栈顶高度与当前位置到栈顶位置之间的宽度，并更新最大矩形面积。
5. 遍历完`heights`后，如果栈中还有元素，则继续计算栈顶高度与当前位置到栈底位置之间的宽度，并更新最大矩形面积。
6. 返回最大矩形面积。

注意，在输入时，我们需要将输入的字符串分割成整数，并将每行的字符串分割成单个整数。最后，将最大矩形面积输出到控制台。
创作类型：
原创

本文链接：题目描述： （注.input（）输入函数的括号中不允许添加任何信息） 时间限制：3000MS 内存限

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share