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

面试算法40:矩阵中的最大矩形

题目

请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如,在图6.6的矩阵中,最大的只包含1的矩阵如阴影部分所示,它的面积是6。
在这里插入图片描述

分析

直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字1,因此将矩阵中上下相邻的值为1的格子看成直方图中的柱子。如果分别以图6.6中的矩阵的每行为基线,就可以得到4个由数字1的格子组成的直方图,如图6.7所示。
在这里插入图片描述

在将矩阵转换成多个直方图之后,就可以计算并比较每个直方图的最大矩形面积,所有直方图中的最大矩形也是整个矩阵中的最大矩形。例如,图6.7(c)的直方图中的最大矩形(阴影部分)也是图6.6中矩阵的最大矩形。

public class Test {public static void main(String[] args) {char[][] matrix = {{'1', '0', '1', '0', '0' },{'0', '0', '1', '1', '1' },{'1', '1', '1', '1', '1' },{'1', '0', '0', '1', '0' }};int result = maximalRectangle(matrix);System.out.println(result);}public static int maximalRectangle(char[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return 0;}int[] heights = new int[matrix[0].length];int maxArea = 0;for (char[] row : matrix) {for (int i = 0; i < row.length; i++) {if (row[i] == '0') {heights[i] = 0;}else {heights[i]++;}}maxArea = Math.max(maxArea, largestRectangleArea(heights));}return maxArea;}public static int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();stack.push(-1);int maxArea = 0;for (int i = 0; i < heights.length; i++) {while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {int height = heights[stack.pop()];int width = i - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}stack.push(i);}while (stack.peek() != -1) {int height = heights[stack.pop()];int width = heights.length - stack.peek() - 1;maxArea = Math.max(maxArea, height * width);}return maxArea;}
}

相关文章:

面试算法40:矩阵中的最大矩形

题目 请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如&#xff0c;在图6.6的矩阵中&#xff0c;最大的只包含1的矩阵如阴影部分所示&#xff0c;它的面积是6。 分析 直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字…...

was下log4j设置日志不输出问题

was下log4j设置日志不输出问题 WAS 也是用的 commons-logging 日志框架 commons-logging 确定 LogFactory 实现的顺序是 从应用的 META-INF/services/org.apache.commons.logging.LogFactory 中获得 LogFactory 实现从系统环境中获得 org.apache.commons.logging.LogFactory…...

小米14系列, OPPO Find N3安装谷歌服务框架,安装Play商店,Google

10月26号小米发布了新款手机小米14,那么很多大家需求问是否支持谷歌服务框架,是否支持Google Play商店gms。因为毕竟小米公司现在安装的系统是HyperOS澎湃OS。但是我拿到手机之后会发现还是开机初始界面会显示power by android,证明这一点他还是支持安装谷歌,包括最近一段时间发…...

Servlet 与Spring对比!

前言&#xff1a; Spring相关的框架知识&#xff0c;算是目前公司在用的前沿知识了&#xff0c;很重要&#xff01;&#xff01; 那么以Spring为基础的框架有几个&#xff1f; 以Spring为基础的框架包括若干模块&#xff0c;其中主要的有Spring Framework、Spring Boot、Spring…...

粤嵌实训医疗项目--day03(Vue + SpringBoot)

往期回顾 粤嵌实训医疗项目day02&#xff08;Vue SpringBoot&#xff09;-CSDN博客 粤嵌实训医疗项目--day01&#xff08;VueSpringBoot&#xff09;-CSDN博客 目录 一、SpringBoot AOP的使用 二、用户模块-注册功能&#xff08;文件上传&#xff09; 三、用户模块-注册实现…...

spark3.3.x处理excel数据

环境: spark3.3.x scala2.12.x 引用: spark-shell --jars spark-excel_2.12-3.3.1_0.18.5.jar 或项目里配置pom.xml <!-- https://mvnrepository.com/artifact/com.crealytics/spark-excel --> <dependency><groupId>com.crealytics</groupId><art…...

哪一个更好?Spring boot还是Node.js

前言 本篇文章有些与众不同&#xff0c;由于我自己手头有些关于这个主题的个人经验&#xff0c;受其启发写出此文。虽然SpringBoot和Node.js服务于很不一样的场景&#xff0c;但是这两个框架共性惊人。其实每种语言都有不计其数的框架&#xff0c;但仅仅一部分是真正卓越的。如…...

AD7321代码SPI接口模数转换连接DAC0832输出verilog

名称&#xff1a;AD7321代码12位ADC&#xff0c;SPI接口模数转换连接DAC0832输出 软件&#xff1a;QuartusII 语言&#xff1a;VHDL 代码功能&#xff1a; 使用VHDL语言编写代码&#xff0c;实现AD7321的控制&#xff0c;将模拟信号转换为数字信号&#xff0c;再经过处理后…...

JavaScript_Pig Game切换当前玩家

const current0El document.getElementById(current--0); const current1El document.getElementById(current--1); if (dice ! 1) {currentScore dice;current0El.textContent currentScore;} else {} });这是我们上个文章写的代码&#xff0c;这个代码明显是有问题的&…...

EtherNet Ip工业RFID读写器与欧姆龙PLC 配置示例说明

一、准备阶段 POE交换机欧姆龙PLC 支持EtherNet Ip协议CX-Programmer 9.5配置软件 二、配置读卡器 1、打开软件 2、选择网卡&#xff0c;如果多网卡的电脑请注意对应所接的网卡&#xff0c;网卡名一般为“Network adapter Realtek PCIe GBE Family” 3、点击“选择网卡”&…...

UE5简化打包大小

UE5.3默认空项目带初学者包的打包后1G多 简化思路&#xff1a; 1.不打包初学者包&#xff08;或者创建时不包括初学者包&#xff0c;跳过第一条&#xff09; 导航&#xff1a;ProjectSettings->Project->Packaging->Packaging->Advanced->List of maps to incl…...

ThinkPHP8学习笔记

ThinkPHP8官方文档地址&#xff1a;ThinkPHP官方手册 一、composer换源 1、查看 composer 配置的命令composer config -g -l 2、禁用默认源镜像命令composer config -g secure-http false 3、修改为阿里云镜像源composer config -g repo.packagist composer https://mirror…...

NSSCTF做题第9页(2)

[SWPUCTF 2022 新生赛]ez_1zpop <?php error_reporting(0); class dxg { function fmm() { return "nonono"; } } class lt { public $impohi; public $md51weclome; public $md52to NSS; function __construct() { $this-&…...

Rust笔记【1】

元组和解构语法 let tup : (i32, f64, u8) (666, 2.0, 1);let tup (666, 2.0, 1); let (x, y, z) tup;let x tup.0; let y tup.1; let z tup.2;数组类型 数组定义是方括号&#xff1a;[ ] 元组定义是小圆括号&#xff1a;( ) 结构体定义是大括号&#xff1a;{ }&#xf…...

代码随想录训练营day3:链表part1

理论 链表的增删操作时间复杂度O(1),查询时间复杂度O(n),因为要从头结点开始。使用场景和数据完全相反 链表的储存地址是不连续的。也和数组不同。 移除链表元素 利用虚拟头结点可以同意操作。不然删除头结点需要额外写。 记得返回的是虚拟头结点的next而不是虚拟头结点retu…...

Bootstrap的咖啡网站实例代码阅读笔记

目录 01-index.html的完整代码02-图片可以通过类 rounded-circle 设置为圆形显示03-<li class"nav-item mt-1 a">中&#xff0c;类mt-1是什么意思&#xff1f;类a又是什么意思&#xff1f;04-href"javascript:void(0);"是什么意思&#xff1f;05-类f…...

2021年06月 Python(二级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试&#xff08;1~6级&#xff09;全部真题・点这里 一、单选题&#xff08;共25题&#xff0c;每题2分&#xff0c;共50分&#xff09; 第1题 执行下列代码后&#xff0c;运行结果是&#xff1f; seq[hello,good,morning] s*.join(seq) print(s)A: hello*good*m…...

FileWriter文件字符输出流

一.概念 以内存为基准&#xff0c;把内存中的数据以字符形式写出到文件中 二.构造器 public FileWriter(Filefile) 创建字节输出流管道与源文件对象接通 public FileWriter(String filepath) 创建字节输出流管道与源文件路径接通 public Filewriter(File file,boolean append) …...

Vue的八个基础命令及作用

1.v-text 作用:获取data数据, 设置标签的内容&#xff0c;以纯文本进行显示v-text 会覆盖 标签中的内容&#xff0c;如果想要拼接数据&#xff0c;可以直接在v-text中拼接如果拼接的是数字&#xff1a;直接使用 “”如果拼接的是字符串&#xff0c;需要使用与外部不同的引号进…...

Log日志详解分析

目录 1、log日志的用途2、log日志级别3、什么时候需要输出日志1. 系统启动参数、环境变量2. 异常捕获处3. 函数获得期望之外的结果时4. 关键操作 4、日志输出的内容5、 注意事项1. 日志信息不明确2. 特殊异常处理3. 日志输出顺序4. 临时调试日志 6、xml文件配置7、linux下查看日…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

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

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