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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...