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

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

思路

最大矩形面积问题可以使用栈来解决,结合柱状图的特性。下面我将详细解释解题思路,并提供关键算法和算法思想的说明。

解题思路:

对于每一行,我们可以将每个元素的值视为当前位置向上的高度。我们可以根据每一行的高度构建一个柱状图,然后使用栈来计算柱状图中的最大矩形面积。

  1. 对于每一行,我们构建一个高度数组 heights,其中 heights[j] 表示从当前行的第 j 列向上的连续 1 的数量。我们可以根据上一行的高度数组和当前行的元素来更新这个数组。

  2. 对于 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 的二维二进制矩阵&#xff0c;找出只包含 1 的最大矩形&#xff0c;并返回其面积。 示例 1&#xff1a; 输入&#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,…...

8.3 【C语言】通过指针引用数组

8.3.1 数组元素的指针 所谓数组元素的指针就是数组元素的地址。 可以用一个指针变量指向一个数组元素。例如&#xff1a; int a[10]{1,3,5,7,9,11,13,15,17,19}&#xff1b; int *p; p&a[0]&#xff1b; 引用数组元素可以用下标法&#xff0c;也可以用指针法&#xf…...

基于Flink CDC实时同步PostgreSQL与Tidb【Flink SQL Client模式下亲测可行,详细教程】

文章目录 一、PostgreSQL作为数据来源&#xff08;source&#xff09;&#xff0c;由flink读取1.postgre安装与配置2.flink安装与配置3.flink cdc postgre配置3.1 postgre配置&#xff08;for flink cdc&#xff09;3.2 flink cdc postgres的jar包下载 4.flink cdc postgre测试…...

Vue-5.编译器Idea

Vue专栏&#xff08;帮助你搭建一个优秀的Vue架子&#xff09; 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.集成&#xff08;.editorconfig、…...

qiuzhiji3

本篇想介绍一下慧与&#xff0c;这里的工作氛围和企业文化令人难忘&#xff0c;希望更多人了解它 也想探讨一下不同的文化铸就的不同企业&#xff0c;究竟有哪些差别。 本篇将从我个人角度出发描述慧与。 2022/3/16至2023/7/31 本篇初次写于2023年8月20日 说起来在毕业之前那段…...

JVM——垃圾回收(垃圾回收算法+分代垃圾回收+垃圾回收器)

1.如何判断对象可以回收 1.1引用计数法 只要一个对象被其他对象所引用&#xff0c;就要让该对象的技术加1&#xff0c;某个对象不再引用其&#xff0c;则让它计数减1。当计数变为0时就可以作为垃圾被回收。 有一个弊端叫做循环引用&#xff0c;两个的引用计数都是1&#xff…...

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前面的代码总和&#xff1a;4.通过POJO获取请求参数 三、解决获取请求参数的乱码问题总结 前言 下面用到了thymeleaf&#xff0c;不知道的可以看…...

【无标题】QT应用编程: QtCreator配置Git版本控制(码云)

QT应用编程: QtCreator配置Git版本控制(码云) 感谢&#xff1a;DS小龙哥的文章&#xff0c;这篇主要参考小龙哥的内容。 https://cloud.tencent.com/developer/article/1930531?areaSource102001.15&traceIdW2mKALltGu5f8-HOI8fsN Qt Creater 自带了git支持。但是一直没…...

JVM面试题-2

1、有哪几种垃圾回收器&#xff0c;各自的优缺点是什么&#xff1f; 垃圾回收器主要分为以下几种&#xff1a;Serial、ParNew、Parallel Scavenge、Serial Old、Parallel Old、CMS、G1&#xff1b; Serial:单线程的收集器&#xff0c;收集垃圾时&#xff0c;必须stop the worl…...

kafka安装说明以及在项目中使用

一、window 安装 1.1、下载安装包 下载kafka 地址&#xff0c;其中官方版内置zk&#xff0c; kafka_2.12-3.4.0.tgz其中这个名称的意思是 kafka3.4.0 版本 &#xff0c;所用语言 scala 版本为 2.12 1.2、安装配置 1、解压刚刚下载的配置文件&#xff0c;解压后如下&#x…...

二叉树搜索

✅<1>主页&#xff1a;我的代码爱吃辣&#x1f4c3;<2>知识讲解&#xff1a;数据结构——二叉搜索树☂️<3>开发环境 &#xff1a;Visual Studio 2022&#x1f4ac;<4>前言&#xff1a;在之前的我们已经学过了普通二叉树&#xff0c;了解了基本的二叉树…...

【先进PID控制算法(ADRC,TD,ESO)加入永磁同步电机发电控制仿真模型研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

k8s集群生产环境的问题处理

2 k8s上的服务均无法访问 执行命令kubectl get pods -ALL,k8s集群中的服务均是running状态 1 kuboard 网页无法访问 kuboard无法通过浏览器访问&#xff0c;但是查看端口是被占用的...

serve : 无法将“serve”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。

1、在学习webpack打包的时候&#xff0c;需要 serve用来启动开发服务器来部署代码查看效果的。安装完之后运行出现以下错误&#xff1a; 2、使用命令查看安装目录&#xff1a; npm list -g我们已经安装过了 3、解决&#xff1a; 我们看到上图路径在&#xff1a;C:\Users\qiy…...

【LVS】2、部署LVS-DR群集

LVS-DR数据包的流向分析 1.客户端发送请求到负载均衡器&#xff0c;请求的数据报文到达内核空间&#xff1b; 2.负载均衡服务器和正式服务器在同一个网络中&#xff0c;数据通过二层数据链路层来传输&#xff1b; 3.内核空间判断数据包的目标IP是本机VIP&#xff0c;此时IP虚…...

设计模式 -- 单例模式(传统面向对象与JavaScript 的对比实现)

单例模式 – 传统面向对象与JavaScript 的对比实现 文章目录 单例模式 -- 传统面向对象与JavaScript 的对比实现传统的面向对象的实现定义实现思路初级实现缺点 透明的单例模式实现目的&#xff08;实现效果&#xff09;实现缺点 用代理实现单例模式优点 JavaScript 中的单例模…...

YOLOX算法调试记录

YOLOX是在YOLOv3基础上改进而来&#xff0c;具有与YOLOv5相媲美的性能&#xff0c;其模型结构如下&#xff1a; 由于博主只是要用YOLOX做对比试验&#xff0c;因此并不需要对模型的结构太过了解。 先前博主调试过YOLOv5,YOLOv7&#xff0c;YOLOv8,相比而言&#xff0c;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)…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

scan_mode设计原则

scan_mode设计原则 在进行mtp controller设计时&#xff0c;基本功能设计完成后&#xff0c;需要设计scan_mode设计。 1、在进行scan_mode设计时&#xff0c;需要保证mtp处于standby模式&#xff0c;不会有擦写、编程动作。 2、只需要固定mtp datasheet说明的接口即可&#xf…...