力扣每日一题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"]]
输出:0

示例 3:

输入:matrix = [["1"]]
输出:1

提示:

  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'

通过次数 198.2K

提交次数 359.2K

通过率 55.2%

思路

把值为1的方格当作一个正方形,把某一层的每个方格作为底,该方格以及上方连续1的个数就是以该方格为底的矩形的面积,这样最大矩形面积就变成了以最下面一层方格作为底,最大柱状图的面积,就转化成了T84。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights){
        heights.push_back(-1);
        stack<int> stk;
        int ans=0;
        for(int i=0;i<heights.size();i++){
            //当遇到右边界时
            while(!stk.empty() && heights[i]<heights[stk.top()]){
                int tall=heights[stk.top()];
                stk.pop();
                int left=stk.empty() ? -1:stk.top();
                ans=max(ans,(i-left-1)*tall);
            }
            stk.push(i);
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows=matrix.size();
        int cols=matrix[0].size();
        vector<vector<int>> heights(rows,vector<int>(cols,0));
        for(int i=0;i<cols;i++){
            if(matrix[0][i]=='1') heights[0][i]=1;
        }
        for(int i=1;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(matrix[i][j]=='1') heights[i][j]=heights[i-1][j]+1;
            }
        }
        int ans=0;
        for(int i=0;i<rows;i++){
            ans=max(ans,largestRectangleArea(heights[i]));
        }
        return ans;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

毫米波SDK使用1

本文档是AM273x等毫米波雷达处理器SDK的配置和使用&#xff0c;主要参考TI的官方文档《mmwave mcuplus sdk user guide》。这里仅摘取其中重要的部分&#xff0c;其余枝节可参考原文。 2 系统概览 mmWave SDK分为两个主要组件:mmWave套件和mmWave演示。 2.1. mmWave套件 mmWa…

react 基础样式的控制(行内和className)

import ./index.cssconst style{color:red,font-size:150px }function App() {return (<div className"App"><h1>行内样式控制</h1><h1 style{{color:red,font-size:150px}} >asd </h1><span style{style} >asd </span>&l…

MATLAB算法实战应用案例精讲-【数模应用】数据孤岛(概念篇)

目录 前言 算法原理 什么是数据孤岛 数据孤岛产生的原因 数据孤岛的问题 什么时候数据孤岛不是坏事&#xff1f; 为什么很难摆脱数据孤岛 数据孤岛对企业造成的负面效应 数据孤岛的影响 数据孤岛的危害 如何解决数据孤岛问题 如何摆脱数据孤岛&#xff1f; 前言 数…

Java学习 - Maven - 常用命令(学习精选)

前言 在上一篇文章中&#xff0c;我们对 Maven 有了初步的了解&#xff0c;包括它的定义、安装步骤以及一些基本的配置方法。Maven 是一个强大的项目管理工具&#xff0c;它可以帮助开发者自动化构建过程&#xff0c;并且管理项目的依赖关系。 今天&#xff0c;我们将深入探讨…

高光谱图像聚类的像素-超像素对比学习与伪标签校正

Pixel-Superpixel Contrastive Learning and Pseudo-Label Correction for Hyperspectral Image Clustering 文章目录 Pixel-Superpixel Contrastive Learning and Pseudo-Label Correction for Hyperspectral Image Clustering摘要引言相关方法对比学习 方法超像素对比学习像素…

攻防世界---misc---Excaliflag

1、题目描述&#xff0c;下载附件是一张图片 2、用winhex分析&#xff0c;没有发现奇怪的地方 3、在kali中使用binwalk -e 命令&#xff0c;虽然分离出来了一些东西&#xff0c;但是不是有用的 4、最后用stegsolve分析&#xff0c;切换图片&#xff0c;发现有字符串&#xff0c…

番外篇 | 利用华为2023最新Gold-YOLO中的Gatherand-Distribute对特征融合模块进行改进

前言:Hello大家好,我是小哥谈。论文提出一种改进的信息融合机制Gather-and-Distribute (GD) ,通过全局融合多层特征并将全局信息注入高层,以提高YOLO系列模型的信息融合能力和检测性能。通过引入MAE-style预训练方法,进一步提高模型的准确性。🌈 目录 🚀1.论文解…

MyBatisPlus总结二

MybatisPlus总结一在这&#xff1a; MybatisPlus总结1/2-CSDN博客 六、分页查询&#xff1a; 6.1.介绍&#xff1a; MybatisPlus内置了分页插件&#xff0c;所以我们只需要配置一个分页拦截器就可以了&#xff0c;由于不同的数据库的分页的方式不一样&#xff0c;例如mysql和…

运维实用小脚本,登录即自动显示系统信息

今天给大家安利一个超级实用的Linux小技巧&#xff0c;让你每次登录终端时都能感受到满满的科技感和效率爆棚&#xff01; 你是否厌倦了每次手动检查系统状态&#xff0c;像内存使用、CPU负载这些繁琐操作&#xff1f;别担心&#xff0c;一个小调整&#xff0c;让这一切自动化…

HC-05蓝牙模块配置连接和使用

文章目录 1. 前期准备 2. 进入AT模式 3. 电脑串口配置 4. 配置过程 5. 主从机蓝牙连接 6. 蓝牙模块HC-05和电脑连接 1. 前期准备 首先需要准备一个USB转TTL连接器&#xff0c;电脑安装一个串口助手&#xff0c;然后按照下面的连接方式将其相连。 VCCVCCGNDGNDRXDTXDTXD…

LeetCode ---400周赛

题目列表 3168. 候诊室中的最少椅子数 3169. 无需开会的工作日 3170. 删除星号以后字典序最小的字符串 3171. 找到按位与最接近 K 的子数组 一、候诊室中的最少椅子数 简单的模拟题&#xff0c;我们可以这样来模拟&#xff1a;当有顾客来时&#xff0c;我们加一把椅子&…

如何使用GPT-4o函数调用构建一个实时应用程序?

本教程介绍了如何使用OpenAI最新的LLM GPT-4o通过函数调用将实时数据引入LLM。 我们在LLM函数调用指南(详见https://thenewstack.io/a-comprehensive-guide-to-function-calling-in-llms/)中讨论了如何将实时数据引入聊天机器人和代理。现在&#xff0c;我们将通过将来自Fligh…

React + SpringBoot实现图片预览和视频在线播放,其中视频实现切片保存和分段播放

图片预览和视频在线播放 需求描述 实现播放视频的需求时&#xff0c;往往是前端直接加载一个mp4文件&#xff0c;这样做法在遇到视频文件较大时&#xff0c;容易造成卡顿&#xff0c;不能及时加载出来。我们可以将视频进行切片&#xff0c;然后分段加载。播放一点加载一点&am…

【稳定检索/投稿优惠】2024年材料科学与能源工程国际会议(MSEE 2024)

2024 International Conference on Materials Science and Energy Engineering 2024年材料科学与能源工程国际会议 【会议信息】 会议简称&#xff1a;MSEE 2024大会地点&#xff1a;中国苏州会议官网&#xff1a;www.iacmsee.com会议邮箱&#xff1a;mseesub-paper.com审稿结…

【基于C++与OpenCV实现魔方图像识别和还原算法】施工总览图

文章目录 主要效果展示思维导图魔方还原算法 本系列博客长期更新&#xff0c;分为两大部分 OpenCV实现魔方六面识别 C编写科先巴二阶段还原算法实现三阶魔方的还原 主要效果展示 摄像头识别六面 3D图像构建&#xff0c;提供还原公式 动画演示还原过程 思维导图 魔方还原算法 参…

Java Web学习笔记26——Element常用组件

常见组件&#xff1a; 就是一个复制和粘贴的过程。 Table表格&#xff1a;用于展示多条结构类的数据&#xff0c;可对数据进行排序、筛选、对比或其他自定义操作。 常见组件-分页主键&#xff1a; Pagination&#xff1a;分页&#xff1a;当数据量比较多时&#xff0c;使用分…

sqlmap直接嗦 dnslog注入 sqllibs第8关

dnslog注入是解决注入的时候没有回显的情况&#xff0c;通过dns外带来进行得到我们想要的数据。 我们是用了dns解析的时候会留下记录&#xff0c;这时候就可以看见我们想要的内容。 这个时候我们还要了解unc路径以及一个函数load_file()以及concat来进行注入。看看我的笔记 unc…

atmel studio 无法通过printf打印浮点数到串口

择右侧的项目,右键,选择properties 系统把它优化了&#xff0c;所以删除&#xff0c;即可 然后&#xff0c;选择相应波特率&#xff0c;效验位&#xff0c;数据位是否正确&#xff0c;即可

Transformer 动画讲解:多层感知机

暑期实习基本结束了&#xff0c;校招即将开启。 不同以往的是&#xff0c;当前职场环境已不再是那个双向奔赴时代了。求职者在变多&#xff0c;HC 在变少&#xff0c;岗位要求还更高了。提前准备才是完全之策。 最近&#xff0c;我们又陆续整理了很多大厂的面试题&#xff0c…

Golang | Leetcode Golang题解之第138题随机链表的复制

题目&#xff1a; 题解&#xff1a; func copyRandomList(head *Node) *Node {if head nil {return nil}for node : head; node ! nil; node node.Next.Next {node.Next &Node{Val: node.Val, Next: node.Next}}for node : head; node ! nil; node node.Next.Next {if…