当前位置: 首页 > 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下查看日…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

ios苹果系统,js 滑动屏幕、锚定无效

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

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

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

【java面试】微服务篇

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