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
思路
最大矩形面积问题可以使用栈来解决,结合柱状图的特性。下面我将详细解释解题思路,并提供关键算法和算法思想的说明。
解题思路:
对于每一行,我们可以将每个元素的值视为当前位置向上的高度。我们可以根据每一行的高度构建一个柱状图,然后使用栈来计算柱状图中的最大矩形面积。
-
对于每一行,我们构建一个高度数组
heights,其中heights[j]表示从当前行的第j列向上的连续 1 的数量。我们可以根据上一行的高度数组和当前行的元素来更新这个数组。 -
对于
heights数组,我们使用栈来辅助计算最大矩形面积。我们遍历heights数组,如果当前高度大于栈顶高度,就将当前索引入栈。否则,我们弹出栈顶索引,并计算以该高度为高的矩形面积,宽度为当前索引与弹出索引之间的距离。我们不断更新最大面积,直到栈为空或者当前高度大于栈顶高度。
关键算法和算法思想:
栈是解决这个问题的关键算法思想。通过使用栈,我们可以维护一个递增的高度序列,当遇到下降的高度时,我们可以计算以当前高度为高的矩形面积,利用栈中保存的索引信息。
代码
object Solution {def maximalRectangle(matrix: Array[Array[Char]]): Int = {if (matrix.isEmpty) return 0val rows = matrix.lengthval cols = matrix(0).lengthvar maxArea = 0val heights = Array.fill(cols)(0)def largestRectangleArea(heights: Array[Int]): Int = {val stack = collection.mutable.Stack[Int]()var maxArea = 0for (i <- 0 until heights.length) {while (stack.nonEmpty && heights(i) < heights(stack.top)) {val height = heights(stack.pop())val width = if (stack.isEmpty) i else i - stack.top - 1maxArea = math.max(maxArea, height * width)}stack.push(i)}while (stack.nonEmpty) {val height = heights(stack.pop())val width = if (stack.isEmpty) heights.length else heights.length - stack.top - 1maxArea = math.max(maxArea, height * width)}maxArea}for (i <- 0 until rows) {for (j <- 0 until cols) {if (matrix(i)(j) == '1') heights(j) += 1else heights(j) = 0}maxArea = math.max(maxArea, largestRectangleArea(heights))}maxArea}
}// 示例
val matrix = Array(Array('1','0','1','0','0'),Array('1','0','1','1','1'),Array('1','1','1','1','1'),Array('1','0','0','1','0')
)
val result = Solution.maximalRectangle(matrix)
println(result) // 输出:6
相关文章:
85-最大矩阵
题目 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,…...
8.3 【C语言】通过指针引用数组
8.3.1 数组元素的指针 所谓数组元素的指针就是数组元素的地址。 可以用一个指针变量指向一个数组元素。例如: int a[10]{1,3,5,7,9,11,13,15,17,19}; int *p; p&a[0]; 引用数组元素可以用下标法,也可以用指针法…...
基于Flink CDC实时同步PostgreSQL与Tidb【Flink SQL Client模式下亲测可行,详细教程】
文章目录 一、PostgreSQL作为数据来源(source),由flink读取1.postgre安装与配置2.flink安装与配置3.flink cdc postgre配置3.1 postgre配置(for flink cdc)3.2 flink cdc postgres的jar包下载 4.flink cdc postgre测试…...
Vue-5.编译器Idea
Vue专栏(帮助你搭建一个优秀的Vue架子) Vue-1.零基础学习Vue Vue-2.Nodejs的介绍和安装 Vue-3.Vue简介 Vue-4.编译器VsCode Vue-5.编译器Idea Vue-6.编译器webstorm Vue-7.命令创建Vue项目 Vue-8.Vue项目配置详解 Vue-9.集成(.editorconfig、…...
qiuzhiji3
本篇想介绍一下慧与,这里的工作氛围和企业文化令人难忘,希望更多人了解它 也想探讨一下不同的文化铸就的不同企业,究竟有哪些差别。 本篇将从我个人角度出发描述慧与。 2022/3/16至2023/7/31 本篇初次写于2023年8月20日 说起来在毕业之前那段…...
JVM——垃圾回收(垃圾回收算法+分代垃圾回收+垃圾回收器)
1.如何判断对象可以回收 1.1引用计数法 只要一个对象被其他对象所引用,就要让该对象的技术加1,某个对象不再引用其,则让它计数减1。当计数变为0时就可以作为垃圾被回收。 有一个弊端叫做循环引用,两个的引用计数都是1ÿ…...
QT TLS initialization failed问题(已解决) QT基础入门【网络编程】openssl
问题: qt.network.ssl: QSslSocket::connectToHostEncrypted: TLS initialization failed 这个问题的出现主要是使用了https请求:HTTPS ≈ HTTP + SSL,即有了加密层的HTTP 所以Qt 组件库需要OpenSSL dll 文件支持HTTPS 解决: 1.加入以下两行代码获取QT是否支持opensll以…...
SpringMVC之获取请求参数
文章目录 前言一、通过ServletAPI获取二、通过控制器方法的形参获取请求参数三、注解1.RequestParam2.RequestHeader3.CookieValue前面的代码总和:4.通过POJO获取请求参数 三、解决获取请求参数的乱码问题总结 前言 下面用到了thymeleaf,不知道的可以看…...
【无标题】QT应用编程: QtCreator配置Git版本控制(码云)
QT应用编程: QtCreator配置Git版本控制(码云) 感谢:DS小龙哥的文章,这篇主要参考小龙哥的内容。 https://cloud.tencent.com/developer/article/1930531?areaSource102001.15&traceIdW2mKALltGu5f8-HOI8fsN Qt Creater 自带了git支持。但是一直没…...
JVM面试题-2
1、有哪几种垃圾回收器,各自的优缺点是什么? 垃圾回收器主要分为以下几种:Serial、ParNew、Parallel Scavenge、Serial Old、Parallel Old、CMS、G1; Serial:单线程的收集器,收集垃圾时,必须stop the worl…...
kafka安装说明以及在项目中使用
一、window 安装 1.1、下载安装包 下载kafka 地址,其中官方版内置zk, kafka_2.12-3.4.0.tgz其中这个名称的意思是 kafka3.4.0 版本 ,所用语言 scala 版本为 2.12 1.2、安装配置 1、解压刚刚下载的配置文件,解压后如下&#x…...
二叉树搜索
✅<1>主页:我的代码爱吃辣📃<2>知识讲解:数据结构——二叉搜索树☂️<3>开发环境 :Visual Studio 2022💬<4>前言:在之前的我们已经学过了普通二叉树,了解了基本的二叉树…...
【先进PID控制算法(ADRC,TD,ESO)加入永磁同步电机发电控制仿真模型研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
k8s集群生产环境的问题处理
2 k8s上的服务均无法访问 执行命令kubectl get pods -ALL,k8s集群中的服务均是running状态 1 kuboard 网页无法访问 kuboard无法通过浏览器访问,但是查看端口是被占用的...
serve : 无法将“serve”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。
1、在学习webpack打包的时候,需要 serve用来启动开发服务器来部署代码查看效果的。安装完之后运行出现以下错误: 2、使用命令查看安装目录: npm list -g我们已经安装过了 3、解决: 我们看到上图路径在:C:\Users\qiy…...
【LVS】2、部署LVS-DR群集
LVS-DR数据包的流向分析 1.客户端发送请求到负载均衡器,请求的数据报文到达内核空间; 2.负载均衡服务器和正式服务器在同一个网络中,数据通过二层数据链路层来传输; 3.内核空间判断数据包的目标IP是本机VIP,此时IP虚…...
设计模式 -- 单例模式(传统面向对象与JavaScript 的对比实现)
单例模式 – 传统面向对象与JavaScript 的对比实现 文章目录 单例模式 -- 传统面向对象与JavaScript 的对比实现传统的面向对象的实现定义实现思路初级实现缺点 透明的单例模式实现目的(实现效果)实现缺点 用代理实现单例模式优点 JavaScript 中的单例模…...
YOLOX算法调试记录
YOLOX是在YOLOv3基础上改进而来,具有与YOLOv5相媲美的性能,其模型结构如下: 由于博主只是要用YOLOX做对比试验,因此并不需要对模型的结构太过了解。 先前博主调试过YOLOv5,YOLOv7,YOLOv8,相比而言,YOLOX的环…...
基于小程序的汽车俱乐部系统的设计与实现(论文+源码)_kaic
目录 前 言 1 系统概述 1.1 系统主要功能 1.2 开发及运行环境 2 系统分析和总体设计 2.1 需求分析 2.2 可行性分析 2.3 设计目标 2.4 项目规划 2.5 系统开发语言简介 2.6 系统功能模块图 3 系统数据库设计 3.1 数据库开发工具简介 3.2 数据库需求分析 3.3 数据库…...
ProgrammingArduino物联网
programming_arduino_ed2 IO 延时闪灯 void setup() {pinMode(13, OUTPUT); }void loop() {digitalWrite(13, HIGH);delay(500);digitalWrite(13, LOW);delay(500); }// sketch 03-02 加入变量 int ledPin 13; int delayPeriod 500;void setup() {pinMode(ledPin, OUTPUT)…...
FPGA信号调试必备:Quartus中keep、preserve、noprune的正确用法与避坑指南
FPGA信号调试必备:Quartus中keep、preserve、noprune的正确用法与避坑指南 在FPGA开发过程中,信号调试是最令人头疼的环节之一。特别是当你发现仿真时明明存在的关键信号,在综合后却神秘消失时,那种挫败感简直难以言表。作为一名长…...
AI系统-7Pytorch数字识别实战及算子介绍
之前铺垫了神经网络的基础知识,这里使用编程工具Pytorch进行一个实战讲解。首先变成一个看得见、摸得着的程序和代码,然后再说后续怎么使用GPU/NPU硬件去优化。 本文主要参考ZOMI酱《AI系统》:https://chenzomi12.github.io/01Introduction/0…...
FLUX.1-dev像素生成器效果对比:不同Scale值对像素结构强度影响实测
FLUX.1-dev像素生成器效果对比:不同Scale值对像素结构强度影响实测 1. 像素艺术生成技术概述 像素幻梦(Pixel Dream Workshop)是基于FLUX.1-dev扩散模型构建的专业像素艺术生成工具。它采用16-bit现代明亮风格设计,为创作者提供…...
3步颠覆性解决方案:零成本条码生成技术让企业彻底告别付费依赖
3步颠覆性解决方案:零成本条码生成技术让企业彻底告别付费依赖 【免费下载链接】librebarcode Libre Barcode: barcode fonts for various barcode standards. 项目地址: https://gitcode.com/gh_mirrors/li/librebarcode Libre Barcode开源字体库通过字体化…...
保姆级教程:在Windows 11上为PyTorch配置CUDA 12.x和cuDNN(含环境变量疑难杂症排查)
Windows 11深度学习环境配置全攻略:从CUDA安装到PyTorch GPU加速实战 每次打开PyCharm准备大展身手时,看到那个令人心碎的False——torch.cuda.is_available()的输出结果,是不是感觉整个深度学习梦想都被泼了冷水?别担心…...
深度解析DiffSinger:基于扩散模型的AI歌声合成技术革命
深度解析DiffSinger:基于扩散模型的AI歌声合成技术革命 【免费下载链接】DiffSinger 项目地址: https://gitcode.com/gh_mirrors/dif/DiffSinger 在当今AI音乐创作领域,DiffSinger歌声合成技术正引领着一场声音生成的技术革命。这个由OpenVPI维护…...
保姆级教程:给你的ClickHouse 23.8装上‘仪表盘’(Prometheus+Grafana监控配置详解)
ClickHouse 23.8全链路监控实战:从Prometheus埋点到Grafana告警设计 当你的ClickHouse集群查询延迟突然从200ms飙升到5秒,是内存不足?磁盘IO瓶颈?还是并发查询堆积?本文将带你构建一套完整的监控告警体系,让…...
开源工具赋能PS4玩家:GoldHEN Cheats Manager的全方位游戏体验优化方案
开源工具赋能PS4玩家:GoldHEN Cheats Manager的全方位游戏体验优化方案 【免费下载链接】GoldHEN_Cheat_Manager GoldHEN Cheats Manager 项目地址: https://gitcode.com/gh_mirrors/go/GoldHEN_Cheat_Manager GoldHEN Cheats Manager是一款专为PlayStation …...
OpenClaw技能开发:为Qwen3-32B定制PDF摘要插件
OpenClaw技能开发:为Qwen3-32B定制PDF摘要插件 1. 为什么需要PDF摘要技能 去年我接手了一个研究项目,需要快速消化上百份行业白皮书和学术论文。每天手动翻阅PDF的日子让我意识到:必须开发一个能自动提取核心观点的工具。这就是我决定为Ope…...
H3C无线调优案例
用户报无线经常掉线,用户现场无线用的H3C 首先登录无线控制器搜集对应接入体验差的AP的诊断日志,从日志中可以看到AP有线上行口的组播广播包数量远远超过了单播报文;没有CRC错误报文,说明网线质量没有问题。接着看:我们…...
