当前位置: 首页 > news >正文

85. 最大矩形

题目描述

给定一个仅包含 01 、大小为 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.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[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 的二维二进制矩阵&#xff0c;找出只包含 1 的最大矩形&#xff0c;并返回其面积。 示例 1&#xff1a; 输入&#xff1a;matrix [["1","0","1","0","0"],["1…...

Vue [Day5]

自定义指令 全局注册 和 局部注册 inserted在指令所在的元素 被插入到页面中时&#xff0c;触发 main.js import Vue from vue import App from ./App.vueVue.config.productionTip false// 1.全局注册指令 Vue.directive(focus, {// inserted在指令所在的元素 被插入到页…...

备战大型攻防演练,“3+1”一套搞定云上安全

在重大活动保障期间&#xff0c;企业不仅要面对愈发灵活隐蔽的新型攻击挑战&#xff0c;还要在人员、精力有限的情况下应对不分昼夜的高强度安全运维任务。如何在这种多重压力下&#xff0c;从“疲于应付”迈向“胸有成竹”呢&#xff1f; 知己知彼&#xff0c;百战不殆&#…...

网络_每日一学——网络的整体概述

今天我们将继续探讨网络相关的知识。网络是由许多设备互相连接而成的&#xff0c;可以传输数据的系统。通过网络&#xff0c;我们可以远程访问他人的计算机、浏览网页、发送电子邮件等。网络是信息时代中不可或缺的一部分。 在网络中&#xff0c;每个设备都有一个唯一的标识符…...

【ChatGPT 指令大全】怎么使用ChatGPT来帮我们写作

在数字化时代&#xff0c;人工智能为我们的生活带来了无数便利和创新。在写作领域&#xff0c;ChatGPT作为一种智能助手&#xff0c;为我们提供了强大的帮助。不论是作文、文章&#xff0c;还是日常函电&#xff0c;ChatGPT都能成为我们的得力助手&#xff0c;快速提供准确的文…...

Redis 如何解决缓存雪崩、缓存击穿、缓存穿透难题

前言 Redis 作为一门热门的缓存技术&#xff0c;引入了缓存层&#xff0c;就会有缓存异常的三个问题&#xff0c;分别是缓存击穿、缓存穿透、缓存雪崩。我们用本篇文章来讲解下如何解决&#xff01; 缓存击穿 缓存击穿: 指的是缓存中的某个热点数据过期了&#xff0c;但是此…...

SSRF(服务器端请求伪造)漏洞

CSRF漏洞与SSRF漏洞的主要区别在于伪造目标的不同。 一、SSRF是什么 SSRF漏洞&#xff1a;&#xff08;Server-Side Request Forgery&#xff0c;服务器端请求伪造&#xff09;是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。一般情况下&#xff0c;SSRF攻击的目标是从…...

【Axure动态面板】利用动态面板实现树形菜单的制作

利用动态面板&#xff0c;简单制作高保真的树形菜单。 一、先看效果 https://1poppu.axshare.com 二、实现思路 1、菜单无非就是收缩和展开&#xff0c;动态面板有个非常好的属性&#xff1a;fit to content&#xff0c;这个属性的含义是&#xff1a;面板的大小可以根据内容多少…...

Android 实现 RecyclerView下拉刷新,SwipeRefreshLayout上拉加载

上拉、下拉的效果图如下&#xff1a; 使用步骤 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&#xff08;MyBatisConfig &#xff09; 对象 实体类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&#xff08;Linux Virtual Server Director Server&#xff09; 名称缩写说明 虚拟IP地址(Virtual IP Address) VIPDirector用于向客户端计算机提供服务的IP地址真实…...

倒计时87天!软考初级信息处理技术员2023下半年报名考试攻略

软考初级信息处理技术员2023下半年报名条件&#xff1a; 1、凡遵守中华人民共和国宪法和各项法律&#xff0c;恪守职业道德&#xff0c;具有一定计算机技术应用能力的人员&#xff0c;均可根据情况报名参加相应专业类别、级别的考试。 2、获准在中华人民共和国境内就业的外籍…...

【腾讯云 Cloud Studio 实战训练营】使用Cloud Studio构建SpringSecurity权限框架

1.Cloud Studio&#xff08;云端 IDE&#xff09;简介 Cloud Studio 是基于浏览器的集成式开发环境&#xff08;IDE&#xff09;&#xff0c;为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装&#xff0c;随时随地打开浏览器就能在线编程。 Clou…...

c语言每日一练(4)

五道选择题 1、有以下代码&#xff0c;程序的输出结果是( ) #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字符转换

都是类型转换&#xff0c;转换成数值类型 VAL是根据情况来系统自动决定转换成什么类型&#xff0c; CDbl是转换成双精度浮点数据类型 VB中C带头的强制转换函数有&#xff1a; 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 函数分析&#xff08;C98&…...

代码随想录算法训练营day56

文章目录 Day56两个字符串的删除操作题目思路代码 编辑距离题目思路代码 Day56 两个字符串的删除操作 583. 两个字符串的删除操作 - 力扣&#xff08;LeetCode&#xff09; 题目 给定两个单词 word1 和 word2&#xff0c;找到使得 word1 和 word2 相同所需的最小步数&#…...

通话降噪算法在手机和IOT设备上的应用和挑战

随着电子产品的升级换代&#xff0c;用户对通话质量的要求也越来越高。通话降噪算法对通话质量起到了关键核心的作用。计算资源的提升使得深度学习模型在便携式的低功耗芯片上面跑起来了&#xff0c;器件成本降低让IoT设备开始使用骨导传感器&#xff0c;&#xff0c;那怎么样才…...

Pet Detection System (PDS)

宠物医院检验设备物联系统...

【OpenCV常用函数:颜色空间转换、阈值化】cv2.cvtColor()+cv2.threshold()

1、cv2.cvtColor() 对图像进行颜色空间的转换 cv2.cvtColor(src, code[, dst[, dstCn]])1) src: 输入图像 2) code: 颜色空间转换编码&#xff0c;常使用的GRAY和RGB之间的转换 cv2.COLOR_BGR2GRAY, cv2.COLOR_RGB2GRAY, cv2.COLOR_GRAY2BGR, cv2.COLOR_GRAY2RGB 3) dst: 输出…...

OpenWRT自动重拨号脚本:5分钟搞定公网IP获取(附定时任务配置)

OpenWRT公网IP自动化获取指南&#xff1a;从脚本编写到策略优化 家里搭建NAS或远程访问服务器时&#xff0c;公网IP就像一把钥匙——没有它&#xff0c;所有设备都锁在内网围墙里。我曾花了整整一周时间研究各家运营商政策&#xff0c;测试了三十多种拨号策略&#xff0c;最终总…...

别再手动调样式了!用WangEditor的Menu API在Vue3里打造你的专属工具栏

深度定制WangEditor&#xff1a;用Menu API在Vue3中构建企业级富文本生态 当我们需要在Vue3项目中集成富文本编辑器时&#xff0c;WangEditor以其轻量级和高度可定制性成为许多开发者的首选。但真正发挥其威力的关键在于深入理解其Menu API系统——这套机制允许我们突破默认功能…...

ComfyUI-WanVideoWrapper全栈指南:从认知到实践的AI视频生成解决方案

ComfyUI-WanVideoWrapper全栈指南&#xff1a;从认知到实践的AI视频生成解决方案 【免费下载链接】ComfyUI-WanVideoWrapper 项目地址: https://gitcode.com/GitHub_Trending/co/ComfyUI-WanVideoWrapper 一、认知篇&#xff1a;理解AI视频生成的技术基础 1.1 核心概念…...

如何用AI润色简历?2026年分步指南与实用技巧

在2026年的求职市场中&#xff0c;简历是连接你与心仪岗位的第一座桥梁。面对日益智能化的招聘系统&#xff08;ATS&#xff09;和快节奏的筛选流程&#xff0c;仅凭一份通用简历已难以脱颖而出。这时&#xff0c;AI润色简历从一种新兴尝试转变为高效、精准的必备策略。本文旨在…...

软考系统分析师必看:数据库设计3大坑点与实战避坑指南(附案例分析)

软考系统分析师数据库设计实战&#xff1a;三大核心陷阱与高阶避坑策略 数据库范式应用的典型误区与修正方案 在航空订票系统的数据库设计中&#xff0c;开发团队曾将机票代理关系模式设计为&#xff08;代理商编号&#xff0c;航班编号&#xff0c;代理商名称&#xff0c;客…...

JetLinks物联网平台TCP接入实战:从零配置到设备上线的完整流程

JetLinks物联网平台TCP接入实战&#xff1a;从零配置到设备上线的完整流程 在物联网应用开发中&#xff0c;设备接入是构建完整解决方案的第一步。JetLinks作为一款开源的物联网平台&#xff0c;提供了灵活的设备接入能力&#xff0c;其中TCP协议因其简单可靠的特点&#xff0c…...

如何用Obsidian构建你的个人知识管理系统:终极完整指南

如何用Obsidian构建你的个人知识管理系统&#xff1a;终极完整指南 【免费下载链接】kepano-obsidian My personal Obsidian vault template. A bottom-up approach to note-taking and organizing things I am interested in. 项目地址: https://gitcode.com/gh_mirrors/ke/…...

阿里云物联网平台OTA升级避坑指南:从版本号上报到Bin文件拉取的全流程排错

阿里云物联网平台OTA升级全链路排错实战手册 当设备固件需要远程更新时&#xff0c;OTA技术无疑是救星。但现实往往比理想骨感——版本号莫名失踪、升级包半路"走失"、设备在关键时刻"装聋作哑"。这些问题不仅耽误进度&#xff0c;更可能让生产线停摆。本文…...

OFA图像描述效果展示:COCO风格caption生成——简洁、准确、自然

OFA图像描述效果展示&#xff1a;COCO风格caption生成——简洁、准确、自然 1. 项目概述 今天要给大家展示一个特别实用的AI工具——基于OFA模型的图像描述生成系统。这个工具能够自动为任何图片生成简洁、准确、自然的英文描述&#xff0c;就像给图片配上了专业的文字说明。…...

Comfy UI Docker 镜像构建实战:从零到部署的完整指南

1. 环境准备与基础配置 在Windows 11上通过WSL搭建Comfy UI开发环境&#xff0c;首先要确保系统版本支持WSL 2。打开PowerShell输入wsl --version检查&#xff0c;如果显示版本低于2.0&#xff0c;需要执行wsl --install进行升级。我推荐使用Ubuntu 22.04作为子系统&#xff0c…...