当前位置:网站首页>leetcode 85.最大矩形 单调栈应用
leetcode 85.最大矩形 单调栈应用
2022-08-10 19:06:00 【Alkali!】
题目描述
最大矩形
给定一个仅包含 0 0 0 和 1 1 1 、大小为 r o w s × c o l s rows \times cols rows×cols 的二维二进制矩阵,找出只包含 1 1 1 的最大矩形,并返回其面积。
思路
这题要从柱状图中最大的矩形中得到思路
- 从矩阵中找出直方图,那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积
- 将矩阵中上下相邻的值为1的格子看成直方图中的柱子
以如下的矩阵为例:
可以按行为基线,划分成四个84题中的柱状图。
这样,求矩阵中面积最大的全1矩形,即是求这所有转化而来的柱状图中最大的矩形面积。
思路:
- 把矩阵的每行看作柱状图,先由原矩阵得到表示柱状图的序列
- 对每行调用84题中的函数,求答案的最大值即可
代码
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0) return 0;
int num=0;
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
if(matrix[i][j]=='1')
num++;
if(num==0) return 0;
//以上为特殊值判断处理
//一定要给二维的vector开辟空间,不然后面不能直接用下标访问
vector<vector<int> > count(matrix.size());
for(int i=0;i<matrix.size();i++)
count[i].resize(matrix[0].size());
//把矩阵的每行看作柱状图,先由原矩阵得到表示柱状图的序列
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
if(i==0)
count[i][j]=matrix[i][j]-'0';
else
{
if(matrix[i][j]=='1')
{
if(matrix[i-1][j]=='1')
count[i][j]=count[i-1][j]+1;
else
count[i][j]=1;
}
else
count[i][j]=0;
}
//调用84题的函数,求最大值
int res=-1;
for(int i=0;i<matrix.size();i++)
res=max(res,largestRectangleArea(count[i]));
return res;
}
int largestRectangleArea(vector<int>& heights) {
vector<int> left,right;
stack<pair<int,int>> s;
for(int i=0;i<heights.size();i++)
{
while(!s.empty()&&s.top().second>=heights[i])
s.pop();
if(s.empty())
left.push_back(-1);
else
left.push_back(s.top().first);
s.push({
i,heights[i]});
}
while(!s.empty()) s.pop();
for(int i=heights.size()-1;i>=0;i--)
{
while(!s.empty()&&s.top().second>=heights[i])
s.pop();
if(s.empty())
right.push_back(heights.size());
else
right.push_back(s.top().first);
s.push({
i,heights[i]});
}
reverse(right.begin(),right.end());
int res=0;
for(int i=0;i<heights.size();i++)
res=max(res,(right[i]-left[i]-1)*heights[i]);
return res;
}
};
边栏推荐
猜你喜欢
转铁蛋白Tf功能化β-榄香烯-雷公藤红素/紫杉醇PLGA纳米粒/雷公藤甲素脂质体(化学试剂)
whois information collection & corporate filing information
工业基础类—利用xBIM提取IFC几何数据
【毕业设计】基于Stm32的智能疫情防控门禁系统 - 单片机 嵌入式 物联网
servlet映射路径匹配解析
Keras深度学习实战(17)——使用U-Net架构进行图像分割
QoS Quality of Service Eight Congestion Avoidance
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
ARouter使用自定义注解处理器,自动生成跳转Activity的代码,避免手动填写和管理path
【无标题】基于Huffman和LZ77的GZIP压缩
随机推荐
mysql 中大小写问题
运维面试题(每日一题)
[教你做小游戏] 斗地主的手牌,如何布局?看25万粉游戏区UP主怎么说
905. 区间选点(贪心)
Rider调试ASP.NET Core时报thread not gc-safe的解决方法
pytorch使用Dataloader加载自己的数据集train_X和train_Y
【CNN】刷SOTA的trick
越折腾越好用的 3 款开源 APP
whois信息收集&企业备案信息
QoS Quality of Service Seven Switch Congestion Management
Optimizing Bloom Filter: Challenges, Solutions, and Comparisons论文总结
皮质-皮质网络的多尺度交流
WCF and TCP message communication practice, c # 】 【 realize group chat function
【深度学习前沿应用】图像风格迁移
新建离线同步节点时选择数据去向-表时报错,数据库类型是adb pg,怎么办?
FEMRL: A Framework for Large-Scale Privacy-Preserving Linkage of Patients’ Electronic Health Rec Paper Summary
QoS服务质量八拥塞避免
怎么完全卸载赛门铁克_Symantec卸载方法,赛门铁克卸载「建议收藏」
[教你做小游戏] 只用几行原生JS,写一个函数,播放音效、播放BGM、切换BGM
Redis 持久化机制