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

代码随想录算法训练营day60|84.柱状图中最大的矩形 |完结撒花~

84.柱状图中最大的矩形

力扣题目链接

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

img

img

  • 1 <= heights.length <=10^5

  • 0 <= heights[i] <= 10^4

  • 暴力解法

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,就会让栈里的所有元素,走到情况三的逻辑。如图:

img

那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑。

开头为什么要加元素0?

如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left。

(mid、left,right 都是对应版本一里的逻辑)

因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。

之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果resutl就是0。 如图所示:

img

所以我们需要在 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 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 1 < heights.length <10^5 0 < heights[i] < 10^…...

在 android 上使用 adb client

adb tool 分为 adb 和 adbd。 adb 用作 host 使用&#xff0c;包含了client和server&#xff0c;adbd 则作为 device 端&#xff0c;在 android 源码目录下&#xff0c;共用一套源码。但 android 源码下的 adb&#xff0c;不支持把 adb 编译为 android 平台的 adb client。因此…...

竞赛选题 基于深度学习的视频多目标跟踪实现

文章目录 1 前言2 先上成果3 多目标跟踪的两种方法3.1 方法13.2 方法2 4 Tracking By Detecting的跟踪过程4.1 存在的问题4.2 基于轨迹预测的跟踪方式 5 训练代码6 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的视频多目标跟踪实现 …...

分布式应用之监控平台zabbix的认识与搭建

一、监控系统的相关知识 1.1 监控系统运用的原因 当我们需要实时关注与其相关的各项指标是否正常&#xff0c;往往存在着很多的服务器、网络设备等硬件资源&#xff0c;如果我们想要能够更加方便的、集中的监控他们&#xff0c;zabix可以实现集中监控管理的应用程序 监控的…...

C语言大佬的必杀技---宏的高级用法

C语言大佬的必杀技—宏的高级用法 目录: 字符串化标记的拼接宏的嵌套替换多条语句防止一个文件被重复包含宏和函数的区别 可能大家在学习的时候用得比较少&#xff0c;但是在一些代码量比较大的时候&#xff0c;这样使用&#xff0c;可以大大的提高代码的可读性&#xff0c;…...

@Retryable和Guava retry

文章目录 一、spring的Retryable1.1 作用&#xff1a;1.2链接&#xff1a;https://www.cnblogs.com/EasonJim/p/7684649.html1.3 坑1.4 Recover补充依赖 二、Guava-retry&#xff1a;使用 一、spring的Retryable 1.1 作用&#xff1a; Retryable注解&#xff0c;被注解的方法…...

conda的安装和使用

参考资料&#xff1a; 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的工作机制&#xff08;1&#xff09;List-Watch的工作机制流程&#xff08;2&#xff09;List-Watch的工作机制图示 3.调度的过程&#xff08;1&#xff09;调度的任务&#xff08;2&#xff09;调度选择p…...

阿里云便宜服务器2核2G配置经济型e实例一年182元性能测评

阿里云服务器经济型e实例2核2G配置优惠价格182.04元一年&#xff0c;系统盘ESSD Entry盘20GB起&#xff0c;公网带宽默认按使用流量&#xff0c;也可以选择按固定带宽计费&#xff0c;带宽值从1M到100M可选&#xff0c;阿腾云分享阿里云服务器2核2G优惠价格、详细配置及e系列CP…...

资讯| 工信部拟筹建元宇宙标准化工作组;《权游》作者起诉OpenAI

元宇宙赛道 工信部&#xff1a;优先开展“元宇宙 工业制造”等行业应用标准研制 9月18日&#xff0c;工业和信息化部科技司就《工业和信息化部元宇宙标准化工作组筹建方案&#xff08;征求意见稿&#xff09;》&#xff08;以下简称《方案》&#xff09;公开征求意见。 工业…...

Win10安装Docker Desktop并运行Tutorial示例

背景 前段时间一个项目需要在开发环境直接使用 Docker &#xff0c;为了省事便计划在本地安装 Desktop 版的 Docker 。其实安装过程比较简单&#xff0c;可视化安装即可&#xff0c;主要是对安装与初步使用时遇到的问题做个记录。 下载安装 下载地址&#xff1a;https://dow…...

1、靶机——Pinkys-Place v3(1)

文章目录 一、环境二、获取flag11、扫描局域网内存活主机1.1 查看kali的IP地址1.2 扫描存活主机 2、粗略扫描靶机端口&#xff08;服务&#xff09;3、寻找ftp服务漏洞4、扫描端口详细信息5、匿名登录ftp 一、环境 攻击机&#xff1a;kali 靶机&#xff1a;Pinkys-Place v3&am…...

【AIGC】Stable Diffusion Prompt 每日一练0916

一、前言 1.1 写在前面 本文是一个系列&#xff0c;有点类似随笔&#xff0c;每天一次更新&#xff0c;重点就Stable Diffusion Prompt进行专项训练&#xff0c;本文是第022篇《Stable Diffusion Prompt 每日一练0916》。上一篇《Stable Diffusion Prompt 每日一练0915》 1.…...

【C语言】指针经典笔试题(上)

C语言的一大重头戏就是指针。 对于指针有一些认识&#xff1a; 1.指针是存放变量的地址&#xff0c;一般说的指针和指针变量是一个概念。 2.地址的单位是字节&#xff0c;大小在不同编译器环境下有所不同&#xff0c;32位机器是4个字节&#xff0c;64位机器是8个字节。 3.数组名…...

缓存问题解决方案

《服务器开发技术、方法与实用解决方案》 一、缓存预热 在系统刚启动或活动刚开始时&#xff0c;如果缓存中没有数据&#xff0c;那么大量请求将直接访问数据库。如果瞬时访问流量巨大&#xff0c;则可能导致数据库因过载而宕机&#xff0c;甚至引发系统雪崩。因此需要将缓存…...

数据结构————寻路算法

(一)基础补充 二维数组 定义:基本概念与方法和一维数组相似,一般形式为:类型符 数组名[常量表达式][常量表达式]; 其中,数组长度只能是常量;通常把二维数组第一个下标理解成行,第二个下标为列,常量表达式: 表达式里面只有常量的式子(如数字类常量); 二维数组常…...

蓝桥杯 题库 简单 每日十题 day7

01 啤酒和饮料 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。啤酒每罐2.3元&#xff0c;饮料每罐1.9元。小明买了若干啤酒和饮料&#xff0c;一共花了82.3元。我们还知道他买的啤酒比饮料的数量少&#xff0c;请你…...

go -- 获取当前24点的时间戳 --chatGpt

gpt: 要获取当前24点的时间戳&#xff0c;你可以使用 Go 标准库中的 time 包来实现。以下是一个示例函数&#xff0c;它可以获取当前日期的24点的时间戳&#xff1a; go package main import ( "fmt" "time" ) func getMidnightTimestamp() in…...

docker 容器内手动设置服务自启动

需求描述&#xff1a;不使用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日完美落幕&#xff0c;40专场活动展示了腾讯最新的前沿技术、核心产品、解决方案。 微服务与消息队列专场&#xff0c;腾讯云微服务平台 TSF 产品经理张桢带来了《腾讯云微服务平台 TSF 异地多活单元化能力重磅升级》的精彩演讲。本…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

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

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

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...