【LeetCode每日一题】——85.最大矩形

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【题目提示】
  • 七【解题思路】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 矩阵

二【题目难度】

  • 困难

三【题目编号】

  • 85.最大矩形

四【题目描述】

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

五【题目示例】

  • 示例 1:

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

    • 输入:matrix = []
    • 输出:0
  • 示例 3:

    • 输入:matrix = [[“0”]]
    • 输出:0
  • 示例 4:

    • 输入:matrix = [[“1”]]
    • 输出:1
  • 示例 5:

    • 输入:matrix = [[“0”,“0”]]
    • 输出:0

六【题目提示】

  • r o w s = = m a t r i x . l e n g t h rows == matrix.length rows==matrix.length
  • c o l s = = m a t r i x [ 0 ] . l e n g t h cols == matrix[0].length cols==matrix[0].length
  • 1 < = r o w , c o l s < = 200 1 <= row, cols <= 200 1<=row,cols<=200
  • m a t r i x [ i ] [ j ] 为 ′ 0 ′ 或 ′ 1 ′ matrix[i][j] 为 '0' 或 '1' matrix[i][j]01

七【解题思路】

  • 首先创建一个辅助数组left,用于记录每个位置的左边连续 ‘1’ 的个数
  • 然后对于二维数组中每一个点,我们计算以这个点作为右下角的矩形的面积,我们利用“向上拓展”的方式,矩阵的宽度是“向上拓展”的过程中最短的宽度,高度通过当前位置减去遍历到的位置然后加一得到(因为数组从零开始计数)
  • 然后通过比较最大值得到最大矩形的面积
  • 最后返回结果即可

八【时间频度】

  • 时间复杂度: O ( m 2 n ) O(m^2n) O(m2n) m 、 n m、n mn分别为传入的二维数组的行数和列数
  • 空间复杂度: O ( m n ) O(mn) O(mn) m 、 n m、n mn分别为传入的二维数组的行数和列数

九【代码实现】

  1. Java语言版
class Solution {public int maximalRectangle(char[][] matrix) {int m = matrix.length;int n = matrix[0].length;int[][] left = new int[m][n];for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '1'){left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int res = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '0'){continue;}int width = left[i][j];int area = width;for(int k = i - 1;k >= 0;k--){width = Math.min(width, left[k][j]);area = Math.max(area,(i - k + 1) * width);}res = Math.max(res, area);}}return res;}
}
  1. C语言版
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize)
{int m = matrixSize;int n = matrixColSize[0];int** left = (int **)malloc(sizeof(int*) * m);for(int i = 0;i < m;i++){left[i] = (int*)calloc(n, sizeof(int));}for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '1'){left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int res = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '0'){continue;}int width = left[i][j];int area = width;for(int k = i - 1;k >= 0;k--){width = fmin(width, left[k][j]);area = fmax(area, (i - k + 1) * width);}res = fmax(res, area);}}return res;
}
  1. Python语言版
class Solution:def maximalRectangle(self, matrix: List[List[str]]) -> int:m = len(matrix)n = len(matrix[0])left = [[0 for _ in range(n)] for _ in range (m)]for i in range(0, m):for j in range(0, n):if matrix[i][j] == '1':left[i][j] = (0 if j == 0 else left[i][j - 1]) + 1res = 0for i in range(0, m):for j in range(0, n):if matrix[i][j] == '0':continuewidth = left[i][j]area = widthfor k in range(i - 1, -1, -1):width = min(width, left[k][j])area = max(area, (i - k + 1) * width)res = max(res, area)return res
  1. C++语言版
class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<vector<int>> left(m, vector<int>(n, 0));for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '1'){left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;}}}int res = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(matrix[i][j] == '0'){continue;}int width = left[i][j];int area = width;for(int k = i - 1;k >= 0;k--){width = fmin(width, left[k][j]);area = fmax(area, (i - k + 1) * width);}res = fmax(res, area);}}return res;}
};

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. C语言版
    在这里插入图片描述

  3. Python语言版
    在这里插入图片描述

  4. C++语言版
    在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79396.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Yolov8-pose关键点检测:模型轻量化设计 | 引入Ghostnet、G_ghost、Ghostnetv2、repghost,进行性能对比

💡💡💡本文解决什么问题:Yolov8-pose关键点评估不同轻量级网络的性能,引入Ghostnet、G_ghost、Ghostnetv2、repghost等网络进行可行性分析 Yolov8-Pose关键点检测专栏介绍:https://blog.csdn.net/m0_63774211/category_12398833.html ✨✨✨手把手教你从数据标记到生…

Python(Web时代)——请求钩子

简介 有时在处理请求之前或之后需要执行一部分代码&#xff0c;比如&#xff1a;创建数据库链接或进行登陆权限认证等&#xff0c;在请求结束时指定数据的交互格式等。 为了避免在每个视图函数中编写重复的代码&#xff0c;flask提供了注册通用函数的功能&#xff08;请求钩子…

windows永久暂停更新

目录 1.winr,输入regedit打开注册表 2.打开注册表的这个路径: 计算机\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 右键空白地方新建QWORD值命名为:FlightSettingsMaxPauseDays 3.双击FlightSettingsMaxPauseDays,修改里面的值为100000,右边基数设置…

17款奔驰S400升级原厂前排座椅通风系统,夏天必备的功能

通风座椅的主动通风功能可以迅速将座椅表面温度降至适宜程度&#xff0c;从而确保最佳座椅舒适性。该功能启用后&#xff0c;车内空气透过打孔皮饰座套被吸入座椅内部&#xff0c;持续时间为 8 分钟。然后&#xff0c;风扇会自动改变旋转方向&#xff0c;将更凉爽的环境空气从座…

Total Variation loss

Total Variation loss 适合任务 图像复原、去噪等 处理的问题 图像上的一点点噪声可能就会对复原的结果产生非常大的影响&#xff0c;很多复原算法都会放大噪声。因此需要在最优化问题的模型中添加一些正则项来保持图像的光滑性&#xff0c;图片中相邻像素值的差异可以通过…

python编写ocr识别图片汉字

当你需要构建一个简单的图形用户界面&#xff08;GUI&#xff09;应用程序&#xff0c;并在其中实现光学字符识别&#xff08;OCR&#xff09;功能时&#xff0c;wxPython是一个强大而灵活的选择。wxPython是一个基于Python的跨平台GUI开发框架&#xff0c;结合了wxWidgets C库…

微信提示操作太频繁怎么办?

微信使用过程中&#xff0c;遇到“操作太频繁”的提示该怎么办&#xff1f; 而提示频繁最常见的两种情况&#xff1a;加好友频繁和发消息频繁。 微信为什么提示频繁&#xff1f;频繁是因为微信故意这样设置的&#xff0c;压根就不想你群发&#xff01;&#xff01;&#xff0…

黑马程序员SpringMVC练手项目

目录 1、需求 2、项目准备 pom.xml SQL jdbc.properties log4j.properties applicationContext.xml spring-mvc.xml web.xml 3、工作流程 4、难点 项目已经上传到gitee&#xff1a;https://gitee.com/xzl-it/my-projects 1、需求 SpringMVC项目练习&#xff1a;数…

bagging集成与boosting集成的区别是什么?

bagging集成与boosting集成的区别 区别一:数据方面 Bagging&#xff1a;对数据进行采样训练; Boosting&#xff1a;根据前一轮学习结果调整数据的重要性。 区别二:投票方面 Bagging&#xff1a;所有学习器平权投票; Boosting&#xff1a;对学习器进行加权投票。 区别三:…

全志D1-H (MQ-Pro)驱动 OV5640 摄像头

内核配置 运行 m kernel_menuconfig 勾选下列驱动 Device Drivers ---><*> Multimedia support --->[*] V4L platform devices ---><*> Video Multiplexer[*] SUNXI platform devices ---><*> sunxi video input (camera csi/mipi…

Android:自己写一个简单记事本

一、前言&#xff1a;我的app是点击加号跳转到另一个界面 那么我遇到的问题的是点击加号是一个从一个Fragment跳转到另一个Fragment跳转失败。 二、解决方案&#xff1a; //相应控件的监听里面实现跳转FragmentManager fragmentManagergetFragmentManager();fragmentManager.b…

react ant icon的简单使用

refer: 快速上手 - Ant Design 1.引入ant npm install antd --save 2.在页面引用&#xff1a; import { StarOutlined } from ant-design/icons; 如果想要引入多个icon&#xff0c;可以这样书写&#xff1a; import { UserOutlined, MailOutlined, PieChartOutlined } fr…

GG修改美食大战老鼠宝石等级以及修改其他资料的方法

这期主要是讲一些&#xff0c;大家修改遇到的问题以及修改其他参数。 宝石、武器如何修改以及软件的安装与配置&#xff0c;请看我gg分栏的前两章 第一点&#xff1a;先讲一下自己武器上宝石等级的问题 宝石的代码&#xff1a; 0级升星宝石的代码1480e010 0级火力宝石的代码1…

MySQL 窗口函数

聚合函数作为窗口函数 设聚合函数为op语法结构&#xff1a; op(字段名A) over(partition by 字段名B order by 字段名C rows between D1 and D2) 其中&#xff1a; partition by&#xff1a;按照某一字段将数据进行分组 order by&#xff1a;按照某一字段将数据进行排序&…

SIP协议之呼叫保持(HOLD)

呼叫保持(HOLD)是SIP协议应用中的一个重要功能&#xff0c;用于实现不挂断电话而达到暂停媒体&#xff08;常见于音频&#xff0c;视频很少用&#xff09;的目的&#xff0c;而解保持操作会恢复通话。 一、保持/解保持实现机制 1.1 保持 保持发起方&#xff08;保持方&#x…

TS协议之PES(ES数据包)

TS协议之PAT&#xff08;节目关联表&#xff09;TS协议之PMT&#xff08;节目映射表&#xff09;TS协议之PES&#xff08;ES数据包&#xff09; 该文档已上传&#xff1a;下载地址 1. 概要 1.1 TS数据包&#xff08;PES&#xff09;协议数据组成 TSTS头PES头ES。TS&#xf…

使用Python将图像转换为PDF:一次性解决您的批量转换需求

导语&#xff1a; 在数字化时代&#xff0c;我们经常需要处理大量的图像文件。将这些图像转换为PDF格式可以方便地存档、分享和打印。本文将介绍如何使用Python编程语言将图像批量转换为PDF&#xff0c;并提供了一个简单易用的图形界面来跟踪转换进度。 准备工作 在开始之前…

uniapp运行项目到iOS基座

2022年9月&#xff0c;因收到苹果公司警告&#xff0c;目前开发者已无法在iOS真机设备使用未签名的标准基座&#xff0c;所以现在要运行到 IOS &#xff0c;也需要进行签名。 Windows系统&#xff0c;HBuilderX 3.6.20以下版本&#xff0c;无法像MacOSX那样对标准基座进行签名…

八、ESP32控制8x8点阵屏

引脚的说明如下 上图中 C表示column 列的意思,所有的C接高电压,即控制esp32中输出1L表示line 行的意思,所有的L接低电压,即控制esp32中输出为01. 运行效果 2. 点阵屏引脚

【Java可执行命令】(十七)JVM运行时信息动态维护工具 jinfo:一个维护 JVM 相关的配置参数和系统属性的工具,辅助故障排除、诊断和优化 ~

Java可执行命令之jinfo 1️⃣ 概念2️⃣ 优势和缺点3️⃣ 使用3.1 语法格式3.2 -flags&#xff1a;查看进程的启动参数3.3 -sysprops&#xff1a;查看进程的系统属性3.4 -flag < name>&#xff1a;查看特定虚拟机参数的值3.5 -flag [/-]< name>&#xff1a;启用或禁…