1158 全是1的最大子矩阵(单调栈)
发布日期:2021-11-02 09:48:37 浏览次数:2 分类:技术文章

本文共 1000 字,大约阅读时间需要 3 分钟。

1158 全是1的最大子矩阵

题目

1158 全是1的最大子矩阵

1.0 秒 131,072.0 KB 40 分 4级题
给出1个M*N的矩阵M1,里面的元素只有0或1,找出M1的一个子矩阵M2,M2中的元素只有1,并且M2的面积是最大的。输出M2的面积。

输入

第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)

第2 - N + 1行:每行m个数,中间用空格分隔,均为0或1。

输出

输出最大全是1的子矩阵的面积。

输入样例

3 3

1 1 0
1 1 1
0 1 1

输出样例

4

代码
#include 
#include
#include
#include
#include
#include
using namespace std;int main() { // 题解 https://blog.csdn.net/zuzhiang/article/details/78693421 stack
st; // h 每一行,a 更新 int m, n, ans = 0, h[2020], a[2020], x; cin >> m >> n; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> x; if (x == 1) { h[j]++; } else { h[j] = 0; } a[j] = h[j]; } a[n + 1] = -1; for (int j = 1; j <= n + 1; j++) { if (st.empty() || a[j] >= a[st.top()]) { // 索引入栈 st.push(j); } else { int top; // 面积值 int area; while (!st.empty() && a[j] < a[st.top()]) { top = st.top(); st.pop(); area = (j - top) * a[top]; ans = max(ans, area); } st.push(top); a[top] = a[j]; } } } cout << ans << endl;}

转载地址:https://blog.csdn.net/weixin_43820352/article/details/108294147 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:1120 机器人走方格 V3(卡特兰数、lucas)
下一篇:51nod 1154 回文串划分(Manacher,dp)

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月15日 02时16分25秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java字符串三目_java字符串连接运算符和三目运算符 2019-04-21
java 堆内存 非堆内存_JVM 堆内存和非堆内存 2019-04-21
Java新手写什么demo_通过入门demo简单了解netty使用方法 2019-04-21
java国际化bundle_java语言国际化--ResouceBundle、struts 2019-04-21
java图片延迟加载_jQuery实现图片延迟加载 2019-04-21
java开发加入购物车功能_java web开发——购物车功能实现 2019-04-21
Java虚拟机不能满足_深入理解Java虚拟机--读书笔记1/3 2019-04-21
python 协程 asyncio_python – asyncio.as_completed是否会产生期货或协同程序? 2019-04-21
java设定xml文件的encoding_配置web-xml解决中文乱码问题,及各种乱码问题集结 2019-04-21
hanlp java api_java分词工具hanlp介绍 2019-04-21
nginx php 源码安装,Nginx1.12.2加php7.2.0的编译安装 2019-04-21
php 删除字节,php – 删除无效/不完整的多字节字符 2019-04-21
php 实现版本号对比,如何在PHP中实现比较版本号 2019-04-21
php sql 给数据库追加内容,php如何向数据库中的某串数据后追加内容【急】 2021-06-24
php微信小程序获取用户信息,微信小程序授权获取用户详细信息openid的实例详解... 2021-06-24
Java三元运算和if,Java三元运算符与<JDK8兼容性中的if / else 2021-06-24
graphql-php enum,php – 如何在不写长查询的情况下查询所有的GraphQL类型字段? 2021-06-24
php date 函数用法,php中date()日期时间函数使用方法 2021-06-24
php除法获取整数和余数,PHP除法取整和取余数 2021-06-24
java迷宫路径,Java中的迷宫路径查找器 2021-06-24