当前位置: 首页 > 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)…...

Stable-Diffusion-v1-5-archive多分辨率实践:512×512 vs 768×768出图质量与耗时对比

Stable-Diffusion-v1-5-archive多分辨率实践&#xff1a;512512 vs 768768出图质量与耗时对比 你是不是也好奇&#xff0c;用Stable Diffusion出图时&#xff0c;分辨率到底该怎么选&#xff1f;是选经典的512512&#xff0c;还是追求更高清的768768&#xff1f;选高了怕电脑跑…...

新手友好:在快马平台用mc、jc相关案例轻松上手前端开发

作为一个刚接触前端开发的新手&#xff0c;我最近在InsCode(快马)平台尝试做了一个特别适合练手的小工具——代码行数统计器。这个项目用最基础的HTML、CSS和JavaScript实现&#xff0c;但包含了前端开发的几个核心概念&#xff0c;特别适合想通过实际案例学习的朋友。 项目功能…...

Mplus实战:如何用随机截距交叉滞后模型(RI-CLPM)分析心理学纵向数据?

Mplus实战&#xff1a;随机截距交叉滞后模型&#xff08;RI-CLPM&#xff09;在心理学纵向研究中的深度应用 心理学研究中&#xff0c;我们常常需要探索变量间的动态相互作用——比如焦虑和睡眠问题如何相互影响&#xff1f;传统交叉滞后模型&#xff08;CLPM&#xff09;虽然广…...

3000 字深度拆解:Paperxie AI 期刊写作界面全解析 —— 科研人必看的 “投刊效率密码”

paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/期刊论文https://www.paperxie.cn/ai/journalArticleshttps://www.paperxie.cn/ai/journalArticles 一、引言&#xff1a;科研人的投稿困局&#xff0c;藏在每一个被忽略的界面细节里 当科研人熬过无数个深…...

告别‘阴阳屏’:深入MTK平台PQ底层,教你用代码实现多供应商屏幕色彩统一

MTK平台屏幕色彩统一实战&#xff1a;从Gamma参数调试到自动化加载 当你的项目同时采用三家不同供应商的屏幕模组时&#xff0c;用户滑动屏幕时可能看到三种截然不同的白色——这种"阴阳屏"现象在硬件采购多元化的今天越来越普遍。作为深耕显示领域多年的工程师&…...

ScanTailor Advanced:3步让你的扫描文档焕然一新

ScanTailor Advanced&#xff1a;3步让你的扫描文档焕然一新 【免费下载链接】scantailor-advanced ScanTailor Advanced is the version that merges the features of the ScanTailor Featured and ScanTailor Enhanced versions, brings new ones and fixes. 项目地址: htt…...

Beyond Compare 5 三步快速激活方案:从评估错误到专业版授权的完整指南

Beyond Compare 5 三步快速激活方案&#xff1a;从评估错误到专业版授权的完整指南 【免费下载链接】BCompare_Keygen Keygen for BCompare 5 项目地址: https://gitcode.com/gh_mirrors/bc/BCompare_Keygen Beyond Compare 5 作为业界领先的文件比对与合并工具&#xf…...

当Navicat密码遗忘时:开源解密工具如何重建数据库连接通路

当Navicat密码遗忘时&#xff1a;开源解密工具如何重建数据库连接通路 【免费下载链接】navicat_password_decrypt 忘记navicat密码时,此工具可以帮您查看密码 项目地址: https://gitcode.com/gh_mirrors/na/navicat_password_decrypt 数据库连接中断的三大痛点场景 场…...

Wireshark抓包实战:DHCP协议交互全流程解析(附常见问题排查)

Wireshark深度解析&#xff1a;DHCP协议交互全流程与实战排错指南 从零开始理解DHCP协议的本质 想象一下&#xff0c;当你带着笔记本电脑走进一家咖啡馆&#xff0c;连接Wi-Fi的瞬间&#xff0c;设备就自动获得了上网所需的所有配置——IP地址、子网掩码、默认网关、DNS服务器。…...

Linux 内核模块编程入门

Linux 内核模块编程入门 内核模块的重要性 作为科技创业者&#xff0c;我深刻理解内核模块在系统开发中的灵活性和强大功能。内核模块允许我们在不重新编译整个内核的情况下&#xff0c;动态地添加或移除功能。这种机制不仅加快了开发迭代速度&#xff0c;还为产品定制化提供了…...