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

简答题

编程实现：

小明有一张矩形彩纸，他将彩纸均匀的画了N*M个小方格，有些小方格中被他画了小草，有些小方格是空白的，现小明想找出一片空白的方格，并且这片空白方格是最大的矩形。

给出N和M的值，及每个方格的状态，被画小草的小方格用数字1表示，空白小方格用数字0表示，请帮小明找出最大矩形，并输出最大矩形由多少个小方格组成。

例如：N=4，M=5，

输入描述：

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

第二行开始，输入N行，每行M个正整数（正整数为1或者0），1表示小草，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 largestRectangleArea(heights):stack = []max_area = 0i = 0while i < len(heights):if not stack or heights[i] >= heights[stack[-1]]:stack.append(i)i += 1else:top = stack.pop()area = heights[top] * (len(stack) if not stack else heights[stack[-1]] - heights[top] + 1)max_area = max(max_area, area)i = top + 1while stack:top = stack.pop()area = heights[top] * (len(stack) if not stack else heights[stack[-1]] - heights[top] + 1)max_area = max(max_area, area)return max_areaN, M = map(int, input().split())grid = []for i in range(N):row = list(map(int, input().split()))grid.append(row)max_area = 0for j in range(M):heights = [0] * Nfor i in range(N):heights[i] = grid[i][j]area = largestRectangleArea(heights)max_area = max(max_area, area)print(max_area)```

解析：

【喵呜刷题小喵解析】：

这个问题可以使用单调栈来解决。对于每一列，我们考虑一个高度数组，其中每个元素表示该列中小草的高度。然后，我们可以使用单调栈来找到最大的矩形面积。

首先，我们遍历每一列，对于每一列，我们创建一个高度数组，其中每个元素表示该列中小草的高度。然后，我们使用单调栈来找到最大的矩形面积。

在单调栈中，我们保持栈顶元素始终为当前遍历到的元素中最小的元素。当遍历到一个新的元素时，如果它大于栈顶元素，我们就不断地从栈中弹出元素，并计算以这些弹出的元素为高的矩形的面积，然后更新最大面积。如果新的元素不大于栈顶元素，我们就将其压入栈中。

最后，我们还需要处理栈中剩余的元素。当遍历完所有元素后，栈中剩余的元素表示以这些元素为高的矩形，我们可以计算它们的面积，并更新最大面积。

最后，我们遍历所有列，找到最大的矩形面积，即为所求。
创作类型：
原创

本文链接：编程实现： 小明有一张矩形彩纸，他将彩纸均匀的画了N*M个小方格，有些小方格中被他画了小草，有些小方

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

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

分享考题
share