代码随想录算法训练营第60天 | 84.柱状图中最大的矩形
单调栈章节理论基础:
https://leetcode.cn/problems/daily-temperatures/
84.柱状图中最大的矩形
题目链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
思路:
本题双指针的写法整体思路和42. 接雨水是一致的,但要比42. 接雨水 难一些。
难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标,而不是左边第一个小于该柱子的高度。
然后右边也是找到第一个小于该柱子的高度。通过示例里的图片应该很好理解。

所以需要循环查找,也就是下面在寻找的过程中使用了while,详细请看下面注释,整理思路在题解:42. 接雨水 中已经介绍了。
代码:
class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] minLeftIndex = new int[n];int[] minRightIndex = new int[n];// 初始化,防止下面while死循环。以及最后的求解minLeftIndex[0] = -1;// 记录每个柱子 左边第一个小于该柱子的下标for(int i=1;i<n;i++){int left = i - 1;while(left >= 0 && heights[left] >= heights[i])left = minLeftIndex[left];minLeftIndex[i] = left;}// 初始化,防止下面while死循环minRightIndex[n-1] = n;// 记录每个柱子 右边第一个小于该柱子的下标for(int i=n-2;i>=0;i--){int right = i + 1;while(right < n && heights[right] >= heights[i])right = minRightIndex[right];minRightIndex[i] = right;}// for(int i=0;i<n;i++){// System.out.print(minLeftIndex[i] + " ");// }// System.out.println();// for(int i=0;i<n;i++){// System.out.print(minRightIndex[i] + " ");// }// 求和int result = 0;for(int i=0;i<n;i++){int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] -1 );result = Math.max(sum,result);}return result;}
}
相关文章:
代码随想录算法训练营第60天 | 84.柱状图中最大的矩形
单调栈章节理论基础: https://leetcode.cn/problems/daily-temperatures/ 84.柱状图中最大的矩形 题目链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/description/ 思路: 本题双指针的写法整体思路和42. 接雨水是一…...
【讲解Node.js常用的命令】进阶版
Node.js常用命令 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行时环境,它使得可以在服务器端运行 JavaScript 代码。Node.js 采用了事件驱动、非阻塞 I/O 模型,非常适用于构建高效的网络应用程序。以下是一些Node.js开发中常用的命令࿱…...
软考81-上午题-【面向对象技术3-设计模式】-行为型设计模式01
一、行为型设计模式一览 二、责任链模式 2-1、意图 使多个对象都有机会处理请求,从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理它为止。 1-2、结构 1-3、代码实现 1-4、适…...
【Linux进阶之路】HTTPS = HTTP + S
文章目录 一、概念铺垫1.Session ID2.明文与密文3.公钥与私钥4.HTTPS结构 二、加密方式1. 对称加密2.非对称加密3.CA证书 总结尾序 一、概念铺垫 1.Session ID Session ID,即会话ID,用于标识客户端与服务端的唯一特定会话的标识符。会话,即客…...
51-31 CVPR’24 | VastGaussian,3D高斯大型场景重建
2024 年 2 月,清华大学、华为和中科院联合发布的 VastGaussian 模型,实现了基于 3D Gaussian Splatting 进行大型场景高保真重建和实时渲染。 Abstract 现有基于NeRF大型场景重建方法,往往在视觉质量和渲染速度方面存在局限性。虽然最近 3D…...
GPT-4引领AI新纪元,Claude3、Gemini、Sora能否跟上步伐?
【最新增加Claude3、Gemini、Sora、GPTs讲解及AI领域中的集中大模型的最新技术】 2023年随着OpenAI开发者大会的召开,最重磅更新当属GPTs,多模态API,未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义,不亚…...
图书馆RFID(射频识别)数据模型压缩/解压缩算法实现小工具
1. 前言 最近闲来无聊,看了一下《图书馆射频识别数据模型第1部分:数据元素的设置及应用规则》以及《图书馆射频识别数据模型第2部分:基于ISO/IEC 15962的数据元素编码方案》,决定根据上面的编码方法实现一下该算法,于…...
【Java Web基础】一些网页设计基础(三)
文章目录 1. 导航栏样式进一步调整2. 入驻企业信息展示栏2.1 Title设置2.2 具体信息添加 3. 轮播图4. 注册登录按钮及其他信息5. 一些五颜六色的、丰富视觉效果的中间件…… 1. 导航栏样式进一步调整 这种导航栏,选中的时候字体变蓝色,可能还是不够美观&…...
2 使用GPU理解并行计算
2.1 简介 本章旨在对并行程序设计的基本概念及其与GPU技术的联系做一个宽泛的介绍。本章主要面向具有串行程序设计经验,但对并行处理概念缺乏了解的读者。我们将用GPU的基本知识来讲解并行程序设计的基本概念。 2.2 传统的串行代码 绝大多数程序员是在串行程序占据…...
Android什么情况下会出现内存泄漏以及怎么解决?
1.什么情况下会出现内存泄漏? (1)单例模式下为什么会造成内存泄漏? 因为单例的生命周期和应用的生命周期是一致的,如果往单例模式里面传了一个生命周期比较短的对象,比如Activity,就会导致Activity不能释放,导致内存泄漏。我们可以传context.getAppliactionContext,而…...
kafka集群介绍及搭建
介绍 kafka是一个高性能、低延迟、分布式的消息传递系统,特点在于实时处理数据。集群由多个成员节点broker组成,每个节点都可以独立处理消息传递和存储任务。 路由策略 发布消息由key、value组成,真正的消息是value,key是标识路…...
2024/03/19(网络编程·day5)
一、思维导图 二、selec函数实现TCP并发服务器 #include<myhead.h>#define SER_PORT 8888 //服务器端口号 #define SER_IP "192.168.117.116" //服务器IP int main(int argc, const char *argv[]) {//1、创建一个套接字int sfd -1;sfd socket(AF_INET,SOC…...
LeetCode解法汇总1969. 数组元素的最小非零乘积
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:. - 力扣(LeetCode) 描述: 给你一个正整数 p 。你有一个下标从 1 开…...
学习vue3第九节(新加指令 v-pre/v-once/v-memo/v-cloak )
1、v-pre 作用:防止编译器解析某个特定的元素及其内容,即v-pre 会跳过当前元素以及其子元素的vue语法解析,并将其保持原样输出; 用于:vue 中一些没有指令和插值表达式的节点的元素,使用 v-pre 可以提高 Vu…...
二开飞机机器人群发,实现自动给多个频道发送消息
频道1 频道2 二开代码部分: const CChatIdListprocess.env.CHANNEL_CHAT_ID_LIST; var channelChatIdArray CChatIdList.split(,);channelChatIdArray.forEach(function(item) {console.log(item); // 这里可以替换为您需要对数组中每个值进行的操作bot.sendM…...
AI如何支持慈善组织
为各种有意义的事业提供支持,无论是努力寻找治愈疾病的方法、研发使生活更轻松的技术,还是为有需要的人提供服务,都是无比崇高的使命。提供捐款或是投入时间支持的捐助者和志愿者往往对他们选择支持的事业的目标、服务和资源分配存有诸多疑虑…...
Git如何清除账户凭证
场景:一般发生在Git用户变更的情况 1.git base 操作 Git会使用凭证助手 credential.helper来储存账户凭证,通过以下命令移除: git config --system --unset credential.helper 除了system系统级外,还有 global、local范围。 查…...
【YUNBEE云贝-PostgreSQL】FDW应用
注: 本文为云贝教育 刘峰 原创,请尊重知识产权,转发请注明出处,不接受任何抄袭、演绎和未经注明出处的转载。 前言 Wrapper(FDW)是一项关键特性,它赋予数据库用户直接通过SQL语句访问存储于外部数据源的能…...
Spring MVC文件上传配置
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl 文件上传 Spring MVC文件上传基于Servlet 3.0实现;示例代码如下: Overrideprotected void customizeRegistration(ServletRegistration.Dynamic reg…...
JavaScript高级(十八)---进程和线程,宏任务和微任务
进程和线程 进程(process):计算机已经运行的程序,是操作系统管理程序的一种方式,我们可以认为,启动一个应用程序,就会默认启动一个进程(也可能是多个进程)。 线程&…...
强化学习在并行机构人形机器人控制中的应用
1. 项目概述在机器人控制领域,强化学习(RL)正逐渐成为解决复杂动力学系统问题的有力工具。然而,当面对具有并行驱动机构的人形机器人时,传统RL训练方法往往面临一个关键挑战:大多数仿真环境无法准确模拟闭环运动链(Closed Kinemat…...
告别虚频困扰:用VASP+DynaPhoPy搞定高温材料声子谱的保姆级教程
高温材料声子谱计算实战:从虚频困境到非谐解决方案 引言:虚频问题的根源与突破路径 在计算材料学领域,声子谱分析是理解材料动力学稳定性和热力学性质的核心手段。然而许多研究者都遭遇过这样的困境:对实验合成的材料进行简谐近似…...
别再只测accuracy!DeepSeek集成测试必须监控的5个隐性指标(P99首token延迟、context bleed率、tool-call schema漂移)
更多请点击: https://intelliparadigm.com 第一章:DeepSeek集成测试的核心范式演进 DeepSeek大模型的工程化落地对集成测试提出了全新挑战:传统基于接口响应码与字段校验的测试范式已难以覆盖语义一致性、推理链鲁棒性、上下文敏感度等高阶质…...
航空航天为什么离不开高强镁合金?国产替代到哪一步了
飞机每减重一千克,全年大约节省四千两百美元的燃油费用——这是航空工程师熟悉的经验值。在商业航空领域,这个数字还只是财务账;在战斗机、导弹和卫星的世界里,减重的收益被换算成更远的航程、更大的载荷、更高的机动性࿰…...
广州因特智能:AI视觉软硬结合,打破半导体检测装备“卡脖子”困境
【导语:广州因特智能科技孵化于西安电子科技大学广州研究院,专注用AI视觉技术解决工业场景的“卡脖子”检测难题,为半导体、光通信、新能源三大领域提供高端检测装备。】校地合作孵化,构建完整能力体系广州因特智能科技由西安电子…...
终极Node.js Mock工具:Mockery入门到精通实战教程
终极Node.js Mock工具:Mockery入门到精通实战教程 【免费下载链接】mockery Simplifying the use of mocks with Node.js 项目地址: https://gitcode.com/gh_mirrors/mock/mockery Mockery是Node.js生态中简化Mock使用的终极工具,它为开发者提供了…...
工业云脑:06 现在就能干:树莓派边缘盒子+PLC,10分钟缺陷检测小案例
06 现在就能干:树莓派边缘盒子+PLC,10分钟缺陷检测小案例 今天第九篇06小节——现在就能干:树莓派边缘盒子+PLC,10分钟缺陷检测小案例。新手照着做10分钟就能跑起来,老手一看就知道这玩意儿省了多少钱。以前想上AI检测,得花几万块买专业边缘盒子;现在?树莓派5(RPi 5)…...
Windows开机自动全屏打开指定网页?一个快捷方式参数就搞定(Chrome/Edge/Firefox教程)
Windows开机自动全屏展示网页的终极方案每次开机都要手动打开浏览器、输入网址、切换全屏模式?这种重复操作不仅浪费时间,还容易在重要演示时手忙脚乱。想象一下:电脑启动后自动全屏显示你的仪表盘、会议日程或是监控大屏,整个过程…...
为什么你明明很努力,领导却总看不到?问题出在这
许多测试同行在深夜加班排查Bug时,在凌晨赶写自动化脚本时,在对着海量数据做性能分析时,内心都会浮现一个共同的困惑:我明明已经这么拼了,为什么在领导眼里,我依然是个“找茬的”,而不是“创造价…...
告别Appium!用Python+UIAutomator2搞定Android自动化测试(附完整环境搭建与实战代码)
PythonUIAutomator2:Android自动化测试的高效实践指南 在移动应用测试领域,效率与稳定性始终是工程师们追求的核心目标。传统方案如Appium虽然功能全面,但在执行速度和资源消耗方面往往难以满足高频测试需求。本文将带您探索基于Python和UIA…...
