面试算法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的矩形并输出它的面积。例如,在图6.6的矩阵中,最大的只包含1的矩阵如阴影部分所示,它的面积是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对比!
前言: Spring相关的框架知识,算是目前公司在用的前沿知识了,很重要!! 那么以Spring为基础的框架有几个? 以Spring为基础的框架包括若干模块,其中主要的有Spring Framework、Spring Boot、Spring…...

粤嵌实训医疗项目--day03(Vue + SpringBoot)
往期回顾 粤嵌实训医疗项目day02(Vue SpringBoot)-CSDN博客 粤嵌实训医疗项目--day01(VueSpringBoot)-CSDN博客 目录 一、SpringBoot AOP的使用 二、用户模块-注册功能(文件上传) 三、用户模块-注册实现…...
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
前言 本篇文章有些与众不同,由于我自己手头有些关于这个主题的个人经验,受其启发写出此文。虽然SpringBoot和Node.js服务于很不一样的场景,但是这两个框架共性惊人。其实每种语言都有不计其数的框架,但仅仅一部分是真正卓越的。如…...

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

JavaScript_Pig Game切换当前玩家
const current0El document.getElementById(current--0); const current1El document.getElementById(current--1); if (dice ! 1) {currentScore dice;current0El.textContent currentScore;} else {} });这是我们上个文章写的代码,这个代码明显是有问题的&…...

EtherNet Ip工业RFID读写器与欧姆龙PLC 配置示例说明
一、准备阶段 POE交换机欧姆龙PLC 支持EtherNet Ip协议CX-Programmer 9.5配置软件 二、配置读卡器 1、打开软件 2、选择网卡,如果多网卡的电脑请注意对应所接的网卡,网卡名一般为“Network adapter Realtek PCIe GBE Family” 3、点击“选择网卡”&…...
UE5简化打包大小
UE5.3默认空项目带初学者包的打包后1G多 简化思路: 1.不打包初学者包(或者创建时不包括初学者包,跳过第一条) 导航:ProjectSettings->Project->Packaging->Packaging->Advanced->List of maps to incl…...

ThinkPHP8学习笔记
ThinkPHP8官方文档地址: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;数组类型 数组定义是方括号:[ ] 元组定义是小圆括号:( ) 结构体定义是大括号:{ }…...
代码随想录训练营day3:链表part1
理论 链表的增删操作时间复杂度O(1),查询时间复杂度O(n),因为要从头结点开始。使用场景和数据完全相反 链表的储存地址是不连续的。也和数组不同。 移除链表元素 利用虚拟头结点可以同意操作。不然删除头结点需要额外写。 记得返回的是虚拟头结点的next而不是虚拟头结点retu…...

Bootstrap的咖啡网站实例代码阅读笔记
目录 01-index.html的完整代码02-图片可以通过类 rounded-circle 设置为圆形显示03-<li class"nav-item mt-1 a">中,类mt-1是什么意思?类a又是什么意思?04-href"javascript:void(0);"是什么意思?05-类f…...

2021年06月 Python(二级)真题解析#中国电子学会#全国青少年软件编程等级考试
Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 执行下列代码后,运行结果是? seq[hello,good,morning] s*.join(seq) print(s)A: hello*good*m…...

FileWriter文件字符输出流
一.概念 以内存为基准,把内存中的数据以字符形式写出到文件中 二.构造器 public FileWriter(Filefile) 创建字节输出流管道与源文件对象接通 public FileWriter(String filepath) 创建字节输出流管道与源文件路径接通 public Filewriter(File file,boolean append) …...
Vue的八个基础命令及作用
1.v-text 作用:获取data数据, 设置标签的内容,以纯文本进行显示v-text 会覆盖 标签中的内容,如果想要拼接数据,可以直接在v-text中拼接如果拼接的是数字:直接使用 “”如果拼接的是字符串,需要使用与外部不同的引号进…...
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的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

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,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...

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

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 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 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗? 在ComfyUI中实现图生视频并延长到5秒,需要结合多个扩展和技巧。以下是完整解决方案: 核心工作流配置(24fps下5秒120帧) #mermaid-svg-yP…...