面试算法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下查看日…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...

【java面试】微服务篇
【java面试】微服务篇 一、总体框架二、Springcloud(一)Springcloud五大组件(二)服务注册和发现1、Eureka2、Nacos (三)负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...