题目:给定一个整型矩阵map,其中的值只有0和1两种,求其中全是1的所有矩形区域中,最大的矩形区域为1的数量。
文章图片
输出: 6
思路:以每一行做切割,统计以当前行作为底的情况下,每个位置往上的连续1的数量,使用高度数组height来表示。
以第一行切割后,height = { 1,0,1,1}.
以第二行切割后,height = { 2,1,2,2}.
以第三行切割后,heigth = { 3,2,3,0}.
用一个栈来存储height数组的下标,当栈为空的时候或当前元素的值大于栈顶元素(height[s.top())的值,直接压入栈。
当栈不为空,且当前元素的值小于或等于栈顶元素时,结算以当前元素的下标为右边界,以栈顶元素下面的那个值为左边界。高度就是当前元素,求得这个矩阵的大小。
后弹出栈顶元素,重复操作,直到当前元素大于栈顶元素或栈为空,压入当前元素。
#include
#include
#include usingnamespace std;
int maxRecFromBotton(int *height, int size)
{
assert(height && size > 0);
int max = 0;
stack s;
for (int i = 0;
i < size;
++i) //遍历这个数组
{
while (!s.empty() && height[i] <= height[s.top()])//等于栈顶元素的时候也要结算。
{
int j = s.top();
s.pop();
int k = s.empty() ? -1 : s.top();
//当栈为空时,左边界为-1,否则为栈顶下面那个值,右边界等于当前元素的下标。
int cur = height[j] * (i - k - 1);
//矩阵的宽度为(i-k-1).因为左边界和右边界都是不可访问的,如左边界为-1,右边界为3,宽度就是【0,1,2】 等于3.
max = cur > max ? cur : max;
}
s.push(i);
//当前元素大于栈顶元素时,直接push
} //当数组遍历完了,别忘了栈中可能还有元素,
while (!s.empty())
{
int j = s.top();
s.pop();
int k = s.empty() ? -1 : s.top();
//左边界。
int cur = height[j] * (size - k - 1);
//当数组遍历完了右边界为数组大小。max = cur > max ? cur : max;
}
return max;
}int maxRecSize(int map[][4], int row)
{
assert(map&& row > 0);
//若条件返回错误,则终止程序执行 int col = 4;
int max = 0;
int *height = new int[col];
memset(height, 0, sizeof(height)*col);
//内存赋值函数,列赋值为0,char以外,只能初始化为0或者-1 for (int i = 0;
i < row;
++i)
{
for (int j = 0;
j < col;
++j)
{
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
//数组的元素表示为以当前行为底,连续1的数量。
}int cur = maxRecFromBotton(height, col);
max = cur > max ? cur : max;
}
return max;
}int main()
{
int map[3][4] = {
{ 1, 0, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 0 }
};
int area = maxRecSize(map, 3);
//面积 cout << area << endl;
cout << "hello..." << endl;
system("pause");
return 0;
}
【求01矩阵的最大面积】
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧(用class类实现链表)
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥(一)2020年第十一届C/C++ B组第二场蓝桥杯省赛真题