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

OJ练习第103题——最大矩形

最大矩形

力扣链接:85. 最大矩形

题目描述

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例

在这里插入图片描述
输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出:6
解释:最大矩形如上图所示。

Java代码(dp)

class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length, n = matrix[0].length;int res = 0;int[][] dp = new int[m+1][n+1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (matrix[i-1][j-1] == '0') continue;dp[i][j] = dp[i][j-1] + 1;int maxArea = dp[i][j], minLength = dp[i][j];for (int height = 2; i >= height && matrix[i-height][j-1] != '0'; height++) {minLength = Math.min(minLength, dp[i-height+1][j]);maxArea = Math.max(maxArea, height * minLength);}res = Math.max(res, maxArea);}}return res;}
}

其他思路

在这里插入图片描述
每一层看作是柱状图,可以套用84. 柱状图中最大的矩形的最大面积。

第一层柱状图的高度[“1”,“0”,“1”,“0”,“0”],最大面积为1;

第二层柱状图的高度[“2”,“0”,“2”,“1”,“1”],最大面积为3;

第三层柱状图的高度[“3”,“1”,“3”,“2”,“2”],最大面积为6;

第四层柱状图的高度[“4”,“0”,“0”,“3”,“0”],最大面积为4;

这一题的算法本质上和 84.题柱状图中最大的矩形 一样,对每一行都求出每个元素对应的高度,这个高度就是对应的连续1的长度,然后对每一行都更新一次最大矩形面积。那么这个问题就变成了85最大矩形。本质上是对矩阵中的每行,均依次执行84题算法。


来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

相关文章:

OJ练习第103题——最大矩形

最大矩形 力扣链接&#xff1a;85. 最大矩形 题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵&#xff0c;找出只包含 1 的最大矩形&#xff0c;并返回其面积。 示例 输入&#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”…...

JavaScript实现输入年份判断是否为闰年的代码

以下为实现输入年份判断是否为闰年的程序代码和运行截图 目录 前言 一、输入年份判断是否为闰年 1.1 运行流程及思想 1.2 代码段 1.3 JavaScript语句代码 1.4 运行截图 前言 1.若有选择&#xff0c;您可以在目录里进行快速查找&#xff1b; 2.本博文代码可以根据题目要…...

LiangGaRy-学习笔记-Day12

1、作业回顾 1.1、判断磁盘利用率 要求&#xff1a; 判断磁盘的使用率&#xff0c;如果超过了90%就警告 [rootNode1 sh]# vim disk_check.sh #!/bin/bash #Author By LiangGaRy #2023年5月9日 #Usage:检测硬盘的使用率 ########################################### #定义一…...

LayUI中弹出层select动态回显设置及子页面刷新父页面Table数据方法

...

浅谈Hutool工具类

一、Hutool简介 Hutool是一个Java工具类库&#xff0c;它封装了很多常用的Java工具类&#xff0c;如加密解密、文件操作、日期时间处理、Http客户端等。它的目标是让Java开发变得更加简单、高效。 二、Hutool的特点 高效&#xff1a;提供了很多高效的工具类和方法。 简单&…...

Mac终端代理

1.打开代理查看代理端口号 打开设置&#xff0c;点击网络&#xff0c;点击详细信息&#xff0c;点击代理查看代理端口号。 2.修改环境变量 1&#xff09;终端输入下面命令 vim .zshrc 2&#xff09;在.zshrc文件里添加下面两段内容&#xff08;注意&#xff1a;7980为端口号…...

Git Clone 报错 `SSL certificate problem: unable to get local issuer certificate`

如果您在尝试克隆Git存储库时得到 “SSL certificate problem: unable to get local issuer certificate” 的错误,这意味着Git无法验证远程存储库的SSL证书。如果SSL证书是自签名的&#xff0c;或者SSL证书链有问题&#xff0c;就会发生这种情况。 $ git clone https://githu…...

第八章 文件与异常

引言 码字不易&#xff0c;如果这篇文章对您有帮助的话&#xff0c;希望您能点赞、收藏、加关注&#xff01;您的鼓励就是我前进的动力&#xff01; 目录 一、读取文件&#xff08;一&#xff09;读取文件&#xff1a;open(), with, read()&#xff08;二&#xff09;文件路径…...

Gradle使用

下载Gradle Gradle Distributions 配置环境变量 测试是否成功 cmd输入gradle -v 在.gradle目录下创建一个init.gradle allprojects { repositories { maven { url file:///D:/maven/myRepository} ## 这里是本地maven仓库地址,没有就会依次向下设置的地址寻…...

从七个方面聊聊Linux到底强在哪

从事计算机相关行业的同学不难发现&#xff0c;身边总有一些朋友在学习linux&#xff0c;有的开发同学甚至自己的电脑就是它。经常听他们说linux如何好用等等。那么linux到底好在那里&#xff0c;能让大家如此喜欢。这也是我经常问自己的一个问题。下面我将通过以下七点来为大家…...

python读写json文件方法详解

在我们日常使用 Python时&#xff0c;经常会使用到 json文件。那么在平时写一些小程序时&#xff0c;如何使用 json文件呢&#xff1f;今天我将介绍如何读取和写入 Json文件。 json是一种数据结构&#xff0c;它是将字符串转换成数据的一种技术。使用 json可以非常方便的将一组…...

多处最优服务次序问题——算法设计与分析(C实现)

问题描述&#xff1a;设有n个顾客同时等待一项服务。顾客i需要的服务时间为&#xff0c;共有s处可以提供此项服务。应该如何安排n个顾客的服务次序&#xff0c;才能使平均等待时间达到最小&#xff1f;平均等待时间是n个顾客的等待服务时间的总和除以n。 算法设计&#xff1a;对…...

2023 年 IntelliJ IDEA 下载安装教程,超详细图文教程,亲测可用

. IDEA 下载 1、打开浏览器输入https://www.jetbrains.com/&#xff0c;进入 Jetbrains官网&#xff0c;点击 Developer Tools&#xff0c;再点击 Intellij IDEA 2、点击中间的 Download&#xff0c;进入IDEA下载界面 3、选择左边的 Ultimate 版本进行下载安装。Ultimate 版…...

前端框架比较:Vue.js、React、AngularJS三者的优缺点和应用场景

章节一&#xff1a;引言 在当前的互联网开发中&#xff0c;前端框架已经成为了不可或缺的一部分。然而&#xff0c;前端框架如此之多&#xff0c;该如何选择呢&#xff1f;Vue.js、React和AngularJS是目前比较受欢迎的三个前端框架&#xff0c;它们各自有着不同的优缺点和应用…...

JavaScript中的数据可视化和动画效果

摘要&#xff1a; JavaScript是一种强大而灵活的编程语言&#xff0c;被广泛用于网页开发和交互设计。在数据可视化和动画效果方面&#xff0c;JavaScript提供了丰富的工具和库&#xff0c;使开发者能够创建出令人印象深刻的交互式数据可视化和动画效果。本文将介绍JavaScript中…...

如何搭建在线产品手册

在现代社会&#xff0c;随着科技的发展&#xff0c;越来越多的企业将目光投向互联网&#xff0c;并将自己的产品推向了线上。而对于这些线上产品&#xff0c;拥有一份完备的、易用、高质量的在线产品手册显得尤为重要。 那么如何才能搭建一份高质量且易用的在线产品手册呢&…...

Java版企业电子采购招标系统源码

一、立项管理 1、招标立项申请 功能点&#xff1a;招标类项目立项申请入口&#xff0c;用户可以保存为草稿&#xff0c;提交。 2、非招标立项申请 功能点&#xff1a;非招标立项申请入口、用户可以保存为草稿、提交。 3、采购立项列表 功能点&#xff1a;对草稿进行编辑&#x…...

【操作系统复习】第6章 虚拟存储器 2

请求分页中的内存分配 在为进程分配物理块时&#xff0c;要解决下列的三个问题&#xff1a; 1. 保证进程可正常运行所需要的最少物理块数 2. 每个进程的物理块数&#xff0c;是固定值还是可变值&#xff08;分配策略&#xff09; 3. 不同进程所分配的物理块数&#xff…...

【OAI】OAI5G核心网VPP-UPF网元分析

文章目录 VPP_UPF_CONFIG_GENERATION.mdVPP UPF Configuration GenerationEnvironment variablesInterfacesInterface Configuration ExamplesCentral UPFA-UPFI-UPFUL CL FEATURE_SET.mdVPP_UPG_CLI参考文献 VPP_UPF_CONFIG_GENERATION.md VPP UPF Configuration Generation …...

【上进小菜猪】使用Ambari提高Hadoop集群管理和开发效率:提高大数据应用部署和管理效率的利器

&#x1f4ec;&#x1f4ec;我是上进小菜猪&#xff0c;沈工大软件工程专业&#xff0c;爱好敲代码&#xff0c;持续输出干货&#xff0c;欢迎关注。 介绍 Hadoop是一种开源的分布式处理框架&#xff0c;用于在一组低成本硬件的集群上存储和处理大规模数据集。Ambari是一种基…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

C++课设:实现本地留言板系统(支持留言、搜索、标签、加密等)

名人说&#xff1a;路漫漫其修远兮&#xff0c;吾将上下而求索。—— 屈原《离骚》 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 专栏介绍&#xff1a;《编程项目实战》 目录 一、项目功能概览与亮点分析1. 核心功能…...