最大空白区题目描述：小明有一张矩形彩纸，他将彩纸均匀的画了N*M个小方格，有些小方格中被他画了小

最大空白区

题目描述：

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

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

例如：N=4，M=5，

输入描述：

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

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

输出描述：

输出一个整数，表示最大矩形由多少个小方格组成

样例输入：

样例输出：

【喵呜刷题小喵解析】：
本题要求找出给定矩形彩纸中的最大空白矩形，并输出其包含的方格数量。根据题目描述，彩纸被均匀划分为N*M个小方格，每个方格的状态用数字1或0表示，其中1表示被画小草，0表示空白。

为了解决这个问题，我们可以使用单调栈的方法。首先，我们遍历每一行，对于每一行，我们计算以每个方格为底边的最大矩形的高度。然后，我们遍历每一列，对于每一列，我们计算以每个方格为右边界的最大矩形的宽度。最后，我们将每个方格作为底边和右边界，计算以该方格为右下角的最大矩形的面积，并更新最大面积。

具体步骤如下：

1. 初始化一个栈，用于存储当前正在处理的行的索引。
2. 遍历每一行，对于每个方格，执行以下操作：
* 如果栈为空，将当前方格的索引压入栈中。
* 如果栈不为空，且栈顶索引对应的方格的状态为0（即空白），则计算以栈顶索引为底边的最大矩形的高度，并将高度乘以当前方格的列索引与栈顶索引的列索引之差，更新最大面积。
* 如果栈不为空，且栈顶索引对应的方格的状态为1（即被画小草），则将当前方格的索引压入栈中。
3. 遍历每一列，对于每个方格，执行以下操作：
* 如果栈为空，将当前方格的列索引压入栈中。
* 如果栈不为空，且栈顶索引对应的方格的状态为0（即空白），则计算以栈顶索引为右边界的最大矩形的宽度，并将宽度乘以当前方格的行索引与栈顶索引的行索引之差，更新最大面积。
* 如果栈不为空，且栈顶索引对应的方格的状态为1（即被画小草），则将栈顶索引弹出，直到栈为空或栈顶索引对应的方格的状态为0。然后，计算以当前方格为右边界的最大矩形的宽度，并将宽度乘以当前方格的行索引与栈顶索引的行索引之差，更新最大面积。
4. 遍历每个方格，对于每个方格，执行以下操作：
* 如果当前方格的状态为0（即空白），则计算以当前方格为右下角的最大矩形的面积，并更新最大面积。

根据题目给出的样例输入，我们可以计算出最大矩形由6个小方格组成。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！