代码随想录算法训练营day60|84.柱状图中最大的矩形 |完结撒花~
84.柱状图中最大的矩形
力扣题目链接
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。


class Solution {public int largestRectangleArea(int[] heights) {int res=0;for(int i=0;i<heights.length;i++){int left=i;int right=i;for(;left>=0;left--){if(heights[left]<heights[i]) break;}for(;right<heights.length;right++){if(heights[right]<heights[i]) break;}int w=right-left-1;int h=heights[i];res=Math.max(res,w*h);}return res;}
}
求左右两边小的, 用单调递减栈
主要就是分析清楚如下三种情况:
- 情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
- 情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
- 情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
头尾要加0 ,如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果的哪一步,所以最后输出的就是0了,那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑。如图:

那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑。
开头为什么要加元素0?
如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left。
(mid、left,right 都是对应版本一里的逻辑)
因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。
之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果resutl就是0。 如图所示:

所以我们需要在 height数组前后各加一个元素0。
整体代码如下:
class Solution {public int largestRectangleArea(int[] heights) {int res=0;int[] newheights=new int[heights.length+2];System.arraycopy(heights,0,newheights,1,heights.length);newheights[0]=0;newheights[heights.length+1]=0;Deque<Integer> stack=new LinkedList<>();stack.push(0);for(int i=1;i<newheights.length;i++){while(!stack.isEmpty()&&newheights[i]<newheights[stack.peek()]){int mid=stack.peek();stack.pop();int w=i-stack.peek()-1;int h=newheights[mid];res=Math.max(res,w*h);}stack.push(i);}return res;}
}
相关文章:
代码随想录算法训练营day60|84.柱状图中最大的矩形 |完结撒花~
84.柱状图中最大的矩形 力扣题目链接 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 1 < heights.length <10^5 0 < heights[i] < 10^…...
在 android 上使用 adb client
adb tool 分为 adb 和 adbd。 adb 用作 host 使用,包含了client和server,adbd 则作为 device 端,在 android 源码目录下,共用一套源码。但 android 源码下的 adb,不支持把 adb 编译为 android 平台的 adb client。因此…...
竞赛选题 基于深度学习的视频多目标跟踪实现
文章目录 1 前言2 先上成果3 多目标跟踪的两种方法3.1 方法13.2 方法2 4 Tracking By Detecting的跟踪过程4.1 存在的问题4.2 基于轨迹预测的跟踪方式 5 训练代码6 最后 1 前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习的视频多目标跟踪实现 …...
分布式应用之监控平台zabbix的认识与搭建
一、监控系统的相关知识 1.1 监控系统运用的原因 当我们需要实时关注与其相关的各项指标是否正常,往往存在着很多的服务器、网络设备等硬件资源,如果我们想要能够更加方便的、集中的监控他们,zabix可以实现集中监控管理的应用程序 监控的…...
C语言大佬的必杀技---宏的高级用法
C语言大佬的必杀技—宏的高级用法 目录: 字符串化标记的拼接宏的嵌套替换多条语句防止一个文件被重复包含宏和函数的区别 可能大家在学习的时候用得比较少,但是在一些代码量比较大的时候,这样使用,可以大大的提高代码的可读性,…...
@Retryable和Guava retry
文章目录 一、spring的Retryable1.1 作用:1.2链接:https://www.cnblogs.com/EasonJim/p/7684649.html1.3 坑1.4 Recover补充依赖 二、Guava-retry:使用 一、spring的Retryable 1.1 作用: Retryable注解,被注解的方法…...
conda的安装和使用
参考资料: https://www.bilibili.com/read/cv8956636/?spm_id_from333.999.0.0 https://www.bilibili.com/video/BV1Mv411x775/?spm_id_from333.999.0.0&vd_source98d31d5c9db8c0021988f2c2c25a9620 目录 conda是啥以及作用conda的安装conda的启动conda的配置…...
K8S:pod集群调度及相关操作
文章目录 一.pod集群调度概念1.调度约束( List-Watch组件)2.List-Watch的工作机制(1)List-Watch的工作机制流程(2)List-Watch的工作机制图示 3.调度的过程(1)调度的任务(2)调度选择p…...
阿里云便宜服务器2核2G配置经济型e实例一年182元性能测评
阿里云服务器经济型e实例2核2G配置优惠价格182.04元一年,系统盘ESSD Entry盘20GB起,公网带宽默认按使用流量,也可以选择按固定带宽计费,带宽值从1M到100M可选,阿腾云分享阿里云服务器2核2G优惠价格、详细配置及e系列CP…...
资讯| 工信部拟筹建元宇宙标准化工作组;《权游》作者起诉OpenAI
元宇宙赛道 工信部:优先开展“元宇宙 工业制造”等行业应用标准研制 9月18日,工业和信息化部科技司就《工业和信息化部元宇宙标准化工作组筹建方案(征求意见稿)》(以下简称《方案》)公开征求意见。 工业…...
Win10安装Docker Desktop并运行Tutorial示例
背景 前段时间一个项目需要在开发环境直接使用 Docker ,为了省事便计划在本地安装 Desktop 版的 Docker 。其实安装过程比较简单,可视化安装即可,主要是对安装与初步使用时遇到的问题做个记录。 下载安装 下载地址:https://dow…...
1、靶机——Pinkys-Place v3(1)
文章目录 一、环境二、获取flag11、扫描局域网内存活主机1.1 查看kali的IP地址1.2 扫描存活主机 2、粗略扫描靶机端口(服务)3、寻找ftp服务漏洞4、扫描端口详细信息5、匿名登录ftp 一、环境 攻击机:kali 靶机:Pinkys-Place v3&am…...
【AIGC】Stable Diffusion Prompt 每日一练0916
一、前言 1.1 写在前面 本文是一个系列,有点类似随笔,每天一次更新,重点就Stable Diffusion Prompt进行专项训练,本文是第022篇《Stable Diffusion Prompt 每日一练0916》。上一篇《Stable Diffusion Prompt 每日一练0915》 1.…...
【C语言】指针经典笔试题(上)
C语言的一大重头戏就是指针。 对于指针有一些认识: 1.指针是存放变量的地址,一般说的指针和指针变量是一个概念。 2.地址的单位是字节,大小在不同编译器环境下有所不同,32位机器是4个字节,64位机器是8个字节。 3.数组名…...
缓存问题解决方案
《服务器开发技术、方法与实用解决方案》 一、缓存预热 在系统刚启动或活动刚开始时,如果缓存中没有数据,那么大量请求将直接访问数据库。如果瞬时访问流量巨大,则可能导致数据库因过载而宕机,甚至引发系统雪崩。因此需要将缓存…...
数据结构————寻路算法
(一)基础补充 二维数组 定义:基本概念与方法和一维数组相似,一般形式为:类型符 数组名[常量表达式][常量表达式]; 其中,数组长度只能是常量;通常把二维数组第一个下标理解成行,第二个下标为列,常量表达式: 表达式里面只有常量的式子(如数字类常量); 二维数组常…...
蓝桥杯 题库 简单 每日十题 day7
01 啤酒和饮料 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。我们还知道他买的啤酒比饮料的数量少,请你…...
go -- 获取当前24点的时间戳 --chatGpt
gpt: 要获取当前24点的时间戳,你可以使用 Go 标准库中的 time 包来实现。以下是一个示例函数,它可以获取当前日期的24点的时间戳: go package main import ( "fmt" "time" ) func getMidnightTimestamp() in…...
docker 容器内手动设置服务自启动
需求描述:不使用DockerFile实现容器内的服务自动启动 1、创建执行程序,以crond为例 //进入容器xxx docker exec -it xxx /bin/sh //切换root账户 bash //创建自动执行文件 vim /root/cron.sh2、自动执行文件内容 crond start3、修改执行文件权限 chmod x /root/…...
腾讯云微服务平台 TSF 异地多活单元化能力重磅升级
导语 2023腾讯全球数字生态大会已于9月7-8日完美落幕,40专场活动展示了腾讯最新的前沿技术、核心产品、解决方案。 微服务与消息队列专场,腾讯云微服务平台 TSF 产品经理张桢带来了《腾讯云微服务平台 TSF 异地多活单元化能力重磅升级》的精彩演讲。本…...
用Segment Anything Model (SAM) 做3D目标检测?手把手教你复现SAM3D论文核心流程
从BEV到3D检测:基于Segment Anything的零样本实践指南 当Meta的Segment Anything Model(SAM)横空出世时,计算机视觉领域掀起了一阵"分割一切"的浪潮。但大多数应用仍停留在2D图像领域,直到SAM3D论文提出将这…...
编译原理实战:5分钟搞定词法分析器的选择题(含答案解析)
编译原理实战:词法分析器选择题高效解题指南 在编译原理的学习和考试中,词法分析器相关选择题往往是考察重点,也是许多同学容易失分的部分。面对复杂的正规式、有限自动机等概念,如何快速准确地做出判断?本文将带你深入…...
大模型数据治理终极指南:5个关键步骤实现高效生命周期管理
大模型数据治理终极指南:5个关键步骤实现高效生命周期管理 【免费下载链接】Foundations-of-LLMs 项目地址: https://gitcode.com/GitHub_Trending/fo/Foundations-of-LLMs 大模型数据治理是构建高质量AI系统的基石,对于确保模型性能、合规性和可…...
Janus-Pro-7B实操手册:批量图片理解任务脚本编写与结果结构化导出
Janus-Pro-7B实操手册:批量图片理解任务脚本编写与结果结构化导出 1. 项目背景与需求场景 在日常工作中,我们经常需要处理大量的图片理解任务。比如电商平台需要分析商品图片中的信息,内容审核团队需要识别图片中的违规内容,或者…...
【学术干货免费领】200+学术海报模板免费领|科研展示零成本,高效出图不内耗 | 学术会议海报模板,适配国际国内各类学术场合 | 硕博研究生必需,全学科适配,助力科研成果高光出圈
重磅福利来袭!200学术海报模板,全程免费领取,零成本解锁科研展示新方式!适配以下各类科研相关人群:硕博研究生群体包括硕士研究生和博士研究生适用于不同研究阶段:从开题报告撰写到学位论文完成特别适合需要…...
各行业开发经验全面解析,本凡科技助你快速提升项目成功率
在当今快速发展的市场中,各行业的开发经验已成为决定项目成败的关键因素。每个行业都面临独特的挑战和需求,了解这些特性有助于企业制定有效的开发策略。例如,科技行业通常需要快速响应市场变化,而食品行业则需关注合规性和安全标…...
先整个经典的入门款耶路撒冷十字电阻吸波器玩吧,就冲5.8GHz的WiFi频段调——毕竟现在连吸波材料都得先蹭蹭网络信号的热度才好入门嘛
CST仿真吸波器选5.8GHz有个小小心思:单层电阻超材料的谐振频率一般和单元边长相关,大概是谐振波长的0.2-0.4倍(等效介电常数εr算进去的话还要除以√εr的平方根),用的FR-4基板ε_r4.4、tanδ0.025、厚度1mm࿰…...
模型微调集成:OpenClaw调用Qwen3-32B的LoRA适配器实战
模型微调集成:OpenClaw调用Qwen3-32B的LoRA适配器实战 1. 为什么需要本地微调模型接入? 去年我在处理一批医疗文献自动化摘要任务时,发现通用大模型对专业术语的理解总差那么一口气。当模型把"冠状动脉搭桥术"解释成"心脏旁…...
极客专属:OpenClaw+百川2-13B打造个人CLI智能助手
极客专属:OpenClaw百川2-13B打造个人CLI智能助手 1. 为什么开发者需要命令行智能助手 作为一个长期与终端打交道的开发者,我每天要重复执行大量机械操作:查看日志、运行测试、整理结果。这些工作虽然简单,却极其消耗精力。直到我…...
Obsidian Local Images Plus 插件使用指南
Obsidian Local Images Plus 插件使用指南 【免费下载链接】obsidian-local-images-plus This repo is a reincarnation of obsidian-local-images plugin which main aim was downloading images in md notes to local storage. 项目地址: https://gitcode.com/gh_mirrors/o…...
