85. 最大矩形
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。
示例 2:
输入:matrix = []
输出:0
示例 3:
输入:matrix = [["0"]]
输出:0
示例 4:
输入:matrix = [["1"]]
输出:1
示例 5:
输入:matrix = [["0","0"]]
输出:0
提示:
rows == matrix.lengthcols == matrix[0].length1 <= row, cols <= 200matrix[i][j]为'0'或'1'
解答
class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {// 利用 84.柱状图中最大的矩形的思路// 在每一行最左边建立一个坐标轴,每列连续1的数量就是矩形高度// 就可以转换为求柱状图中最大的矩形if(matrix.size() == 0){return 0;}vector<int> heights(matrix[0].size());int maxArea;// 每一行都求一次最大矩形for(int row = 0; row < matrix.size(); row++){// 求出某一行每列的高度for(int col = 0; col < matrix[0].size(); col++){if(matrix[row][col] == '1'){heights[col] += 1;}else // 同一列1不连续,高度重置为1{heights[col] = 0;}}maxArea = max(maxArea, largestRectangleArea(heights));}return maxArea;}// 求每行的最大矩形int largestRectangleArea(vector<int> &heights){int maxArea = 0;stack<int> st;int p = 0;while(p < heights.size()){// 栈空入栈if(st.empty()){st.push(p);p++;}else {int top = st.top();// 当前高度大于栈顶入栈// 保证栈顶到栈底降序if(heights[p] >= heights[top]){st.push(p);p++;}else // 当前高度小于小于栈顶对应的右边界,出栈{int height = heights[st.top()];st.pop();// 左边第一个小于当前柱子的下标int left = st.empty() ? -1 : st.top();// 右边第一个小于当前柱子的下标int right = p;maxArea = max(maxArea, (right - left - 1) * height);}}}// 【左边界】从【右往左】扩展进行判断是否得到最大矩形while(!st.empty()) // 柱状图完全递增的情况{int height = heights[st.top()];st.pop();// 左边第一个小于当前柱子下标int left = st.empty() ? -1 : st.top();// 右边没有小于当前高度的柱子int right = heights.size();maxArea = max(maxArea, (right - left - 1) * height);}return maxArea;}
};
相关文章:
85. 最大矩形
题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix [["1","0","1","0","0"],["1…...
Vue [Day5]
自定义指令 全局注册 和 局部注册 inserted在指令所在的元素 被插入到页面中时,触发 main.js import Vue from vue import App from ./App.vueVue.config.productionTip false// 1.全局注册指令 Vue.directive(focus, {// inserted在指令所在的元素 被插入到页…...
备战大型攻防演练,“3+1”一套搞定云上安全
在重大活动保障期间,企业不仅要面对愈发灵活隐蔽的新型攻击挑战,还要在人员、精力有限的情况下应对不分昼夜的高强度安全运维任务。如何在这种多重压力下,从“疲于应付”迈向“胸有成竹”呢? 知己知彼,百战不殆&#…...
网络_每日一学——网络的整体概述
今天我们将继续探讨网络相关的知识。网络是由许多设备互相连接而成的,可以传输数据的系统。通过网络,我们可以远程访问他人的计算机、浏览网页、发送电子邮件等。网络是信息时代中不可或缺的一部分。 在网络中,每个设备都有一个唯一的标识符…...
【ChatGPT 指令大全】怎么使用ChatGPT来帮我们写作
在数字化时代,人工智能为我们的生活带来了无数便利和创新。在写作领域,ChatGPT作为一种智能助手,为我们提供了强大的帮助。不论是作文、文章,还是日常函电,ChatGPT都能成为我们的得力助手,快速提供准确的文…...
Redis 如何解决缓存雪崩、缓存击穿、缓存穿透难题
前言 Redis 作为一门热门的缓存技术,引入了缓存层,就会有缓存异常的三个问题,分别是缓存击穿、缓存穿透、缓存雪崩。我们用本篇文章来讲解下如何解决! 缓存击穿 缓存击穿: 指的是缓存中的某个热点数据过期了,但是此…...
SSRF(服务器端请求伪造)漏洞
CSRF漏洞与SSRF漏洞的主要区别在于伪造目标的不同。 一、SSRF是什么 SSRF漏洞:(Server-Side Request Forgery,服务器端请求伪造)是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。一般情况下,SSRF攻击的目标是从…...
【Axure动态面板】利用动态面板实现树形菜单的制作
利用动态面板,简单制作高保真的树形菜单。 一、先看效果 https://1poppu.axshare.com 二、实现思路 1、菜单无非就是收缩和展开,动态面板有个非常好的属性:fit to content,这个属性的含义是:面板的大小可以根据内容多少…...
Android 实现 RecyclerView下拉刷新,SwipeRefreshLayout上拉加载
上拉、下拉的效果图如下: 使用步骤 1、在清单文件中添加依赖 implementation ‘com.android.support:recyclerview-v7:27.1.1’ implementation “androidx.swiperefreshlayout:swiperefreshlayout:1.0.0” 2、main布局 <LinearLayout xmlns:android"http…...
使用MethodInterceptor和ResponseBodyAdvice做分页处理
目录 一、需求 二、代码实现 父pom文件 pom文件 配置文件 手动注册SqlSessionFactory(MyBatisConfig ) 对象 实体类Users 抽象类AbstractQuery 查询参数类UsersQuery 三层架构 UsersController UsersServiceImpl UsersMapper UsersMapper.…...
WEB集群——LVS-DR 群集、nginx负载均衡
1、基于 CentOS 7 构建 LVS-DR 群集。 2、配置nginx负载均衡。 一、 LVS-DR 群集 1、LVS-DR工作原理 LVS-DR(Linux Virtual Server Director Server) 名称缩写说明 虚拟IP地址(Virtual IP Address) VIPDirector用于向客户端计算机提供服务的IP地址真实…...
倒计时87天!软考初级信息处理技术员2023下半年报名考试攻略
软考初级信息处理技术员2023下半年报名条件: 1、凡遵守中华人民共和国宪法和各项法律,恪守职业道德,具有一定计算机技术应用能力的人员,均可根据情况报名参加相应专业类别、级别的考试。 2、获准在中华人民共和国境内就业的外籍…...
【腾讯云 Cloud Studio 实战训练营】使用Cloud Studio构建SpringSecurity权限框架
1.Cloud Studio(云端 IDE)简介 Cloud Studio 是基于浏览器的集成式开发环境(IDE),为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装,随时随地打开浏览器就能在线编程。 Clou…...
c语言每日一练(4)
五道选择题 1、有以下代码,程序的输出结果是( ) #include <stdio.h> int main() {int a 0, b 0;for (a 1, b 1; a < 100; a){if (b > 20) break;//1if (b % 3 1)//2{b b 3;continue;}b b-5;//3}printf("%d\n", a);return 0; } A.1…...
VB字符转换
都是类型转换,转换成数值类型 VAL是根据情况来系统自动决定转换成什么类型, CDbl是转换成双精度浮点数据类型 VB中C带头的强制转换函数有: CBool(expression) ---- 转换成布尔型 CByte(expression) ---- 转换成字节型 CCur(expression) --…...
【C++进阶之路】map与set的基本使用
文章目录 一、set系列1.set①insert②find③erase④lower_bound与upper_bound 2.multiset①count②equal_range 二、map系列1.map①insert1.插入pair的四种方式2.常用两种方式 ②[]2.multimap①count②equal_range 一、set系列 1.set ①insert 函数分析(C98&…...
代码随想录算法训练营day56
文章目录 Day56两个字符串的删除操作题目思路代码 编辑距离题目思路代码 Day56 两个字符串的删除操作 583. 两个字符串的删除操作 - 力扣(LeetCode) 题目 给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数&#…...
通话降噪算法在手机和IOT设备上的应用和挑战
随着电子产品的升级换代,用户对通话质量的要求也越来越高。通话降噪算法对通话质量起到了关键核心的作用。计算资源的提升使得深度学习模型在便携式的低功耗芯片上面跑起来了,器件成本降低让IoT设备开始使用骨导传感器,,那怎么样才…...
Pet Detection System (PDS)
宠物医院检验设备物联系统...
【OpenCV常用函数:颜色空间转换、阈值化】cv2.cvtColor()+cv2.threshold()
1、cv2.cvtColor() 对图像进行颜色空间的转换 cv2.cvtColor(src, code[, dst[, dstCn]])1) src: 输入图像 2) code: 颜色空间转换编码,常使用的GRAY和RGB之间的转换 cv2.COLOR_BGR2GRAY, cv2.COLOR_RGB2GRAY, cv2.COLOR_GRAY2BGR, cv2.COLOR_GRAY2RGB 3) dst: 输出…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
