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

代码随想录打卡第六十三天|84.柱状图中最大的矩形

84.柱状图中最大的矩形

题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。
在这里插入图片描述
在这里插入图片描述
提示:

1 <= heights.length <=105
0 <= heights[i] <= 104

题目链接:84.柱状图中最大的矩形

//单调栈
class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;Stack<Integer> stack=new Stack<Integer>();int ans=0;//要找左边右边第一个比当前柱子小的元素//维护单调递增栈//求左边第一个 栈中的是左侧元素 弹出比它大的 栈顶就是比它小的第一个元素int[] left=new int[heights.length];int[] right=new int[heights.length];stack.push(0);left[0]=-1;for(int i=1;i<heights.length;i++){while(!stack.isEmpty()&&heights[i]<=heights[stack.peek()]){stack.pop();}if(stack.isEmpty()){left[i]=-1;}else{left[i]=stack.peek();}stack.push(i);}stack.clear();for (int i = n - 1; i >= 0; --i) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}right[i] = (stack.isEmpty() ? n : stack.peek());stack.push(i);}for (int i = 0; i < n; ++i) {ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans;}//单调栈优化//维护一个递增的栈 当入站元素小于栈顶元素时 栈顶元素左边第一个比他小的和右边第一个比它小的都找齐了 直接计算面积即可public int largestRectangleArea(int[] heights) {int[] newheights = new int[heights.length + 1];System.arraycopy(heights,0,newheights,0,heights.length);newheights[newheights.length-1]=0;int n = newheights.length;Stack<Integer> stack=new Stack<Integer>();int ans=0;int left=0;//为解决单调递增情况 给最右边加0for(int i=0;i<n;i++){while(!stack.isEmpty()&&newheights[i]<newheights[stack.peek()]){int mid=newheights[stack.peek()];stack.pop();if(!stack.isEmpty()){left=stack.peek(); }else{left=-1;}ans=Math.max(ans,(i-left-1)*mid);}stack.push(i);}return ans;}
}

相关文章:

代码随想录打卡第六十三天|84.柱状图中最大的矩形

84.柱状图中最大的矩形 题目&#xff1a;给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 提示&#xff1a; 1 < heights.length <105 0 < h…...

python tempfile 模块使用

在Python中&#xff0c;tempfile 模块用于创建临时文件和目录&#xff0c;它们可以用于存储中间处理数据&#xff0c;不需要长期保存。该模块提供了几种不同的类和函数来创建临时文件和目录。 下面是几个常用的 tempfile 使用方法&#xff1a; 临时文件 使用 NamedTemporary…...

【软件测试】接口测试实战详解

最近找到了几个问题&#xff0c;都还比较有代表性。 作为一个初级测试&#xff0c;想学接口测试&#xff0c;但是一点头绪都没有。求教大神指点&#xff0c;有没有好的书或者工具推荐&#xff1f;如何做接口测试呢&#xff1f;接口测试有哪些工具做接口测试的流程一般是怎么样…...

轻量封装WebGPU渲染系统示例<20>- 美化一下元胞自动机之生命游戏(源码)

当前示例源码github地址: https://github.com/vilyLei/voxwebgpu/blob/feature/rendering/src/voxgpu/sample/GameOfLifePretty.ts 系统特性: 1. 用户态与系统态隔离。 2. 高频调用与低频调用隔离。 3. 面向用户的易用性封装。 4. 渲染数据(内外部相关资源)和渲染机制分离…...

Nodejs的安装以及配置(node-v12.16.1-x64.msi)

Nodejs的安装以及配置 1、安装 node-v12.16.1-x64.msi点击安装&#xff0c;注意以下步骤 本文设置nodejs的安装的路径&#xff1a;D:\soft\nodejs 继续点击next&#xff0c;选中Add to PATH &#xff0c;旁边的英文告诉我们会把 环境变量 给我们配置好 当然也可以只选择 Nod…...

03【保姆级】-GO语言变量和数据类型和相互转换

03【保姆级】-GO语言变量和数据类型 一、变量1.1 变量的定义&#xff1a;1.2 变量的声明、初始化、赋值1.3 变量使用的注意事项 插播-关于fmt.Printf格式打印%的作用二、 变量的数据类型2.1整数的基本类型2.1.1 有符号类型 int8/16/32/642.1.2 无符号类型 int8/16/32/642.1.3 整…...

mermaid学习第一天/更改主题颜色和边框颜色/《需求解释流程图》

mermaid 在线官网&#xff1a; https://mermaid-js.github.io/ 在线学习文件&#xff1a; https://mermaid.js.org/syntax/quadrantChart.html 1、今天主要是想做需求解释的流程图&#xff0c;又不想自己画&#xff0c;就用了&#xff0c;框框不能直接进行全局配置&#xff0…...

SAP MASS增加PR字段-删除标识

MASS->BUS2105->发现没有找到PR删除标识字段 SAP MASS增加PR字段-删除标识 1.tcode:MASSOBJ 选中BUS2105 点“应用程序表” 点“字段列表” 2.选中一行进行参考 3.修改字段为删除标识 LOEKZ&#xff0c;保存即可。 4.然后MASS操作&#xff0c;批量设置删除标识&…...

【手把手教你】训练YOLOv8分割模型

1.下载文件 在github上下载YOLOV8模型的文件&#xff0c;搜索yolov8&#xff0c;star最多这个就是 2. 准备环境 环境要求python>3.8&#xff0c;PyTorch>1.8&#xff0c;自行安装ptyorch环境即可 2. 制作数据集 制作数据集&#xff0c;需要使用labelme这个包&#…...

物料主数据增强屏幕绘制器DUMP

问题描述 在做完物料主数据增强后&#xff0c;配置和代码传Q&#xff0c;在Q进入增强屏幕绘制器报错。 错误 CALLBACK_REJECTED_BY_WHITELIST RFC callback call rejected by positive list An RFC callback has been prevented due to no corresponding positive list en…...

vue 实现在线预览Excel-LuckyExcel/LuckySheet实现方案

一、准备工作 1. npm安装 luckyexcel npm i -D luckyexcel 2.引入luckysheet 注意&#xff1a;引入luckysheet&#xff0c;只能通过CDN或者直接引入静态资源的形式&#xff0c;不能npm install。 个人建议直接下载资源引入。我给你们提供一个下载资源的地址&#xff1a; …...

AIGPT重大升级,界面重新设计,功能更加饱满,用户体验升级

AIGPT AIGPT是一款功能强大的人工智能技术处理软件&#xff0c;不但拥有其他模型处理文本认知的能力还有AI绘画模型、拥有自身的插件库。 我们都知道使用ChatGPT是需要账号以及使用魔法的&#xff0c;实现其中的某一项对我们一般的初学者来说都是一次巨大的挑战&#xff0c;但…...

Web逆向-mtgsig1.2简单分析

{"a1": "1.2", # 加密版本"a2": new Date().valueOf() - serverTimeDiff, # 加密过程中用到的时间戳. 这次服主变坏了, 时间戳需要减去一个 serverTimeDiff(见a3) ! "a3": "这是把xxx信息加密后提交给服务器, 服主…...

【蓝桥杯省赛真题41】Scratch电脑开关机 蓝桥杯少儿编程scratch图形化编程 蓝桥杯省赛真题讲解

目录 scratch电脑开关机 一、题目要求 编程实现 二、案例分析 1、角色分析...

第10章 Java常用类

目录 内容说明 章节内容 一、Object类 二、String类和StringBuffer类 三、Math类和Random类...

Android 11 getPackageManager().getPackageInfo 返回null

Android11 之后&#xff0c; 在查找用户手机是否有安装app&#xff0c;进行查询包名是否存在时&#xff0c;getPackageManager().getPackageInfo&#xff08;&#xff09;这个函数一直返回null &#xff0c;Android 11增加了权限要求。 1、只是查询指定的App 包 只需要在Andro…...

4、数据结构

数据结构01 数值处理 取整 日常用的四种 / 整数除法&#xff0c;截取整数部分math.Ceil 向上取整 “理解为天花板&#xff0c;向上取值”math.Floor 向下取整 “理解为地板&#xff0c;向下取值”math.Round 四舍五入 / 整数除法&#xff0c;截取整数部分 func main() { f…...

qt5.15.2+vs2019源码调试开发环境搭建

说明 一些qt文件不进行源码调试无法知道其中的原理。提高软件质量&#xff0c;从概念原理及应用角度看待必须知道qt类运行原理。 1.安装 在网上找到qt安装包qt-unified-windows-x64-4.5.1-online.exe&#xff0c;安装qt5.15.2&#xff0c;有选择Qt Debug Information Files …...

【数据结构】单链表之--无头单向非循环链表

前言&#xff1a;前面我们学习了动态顺序表并且模拟了它的实现&#xff0c;今天我们来进一步学习&#xff0c;来学习单链表&#xff01;一起加油各位&#xff0c;后面的路只会越来越难走需要我们一步一个脚印&#xff01; &#x1f496; 博主CSDN主页:卫卫卫的个人主页 &#x…...

网络中使用最多的图片格式有哪些

互联网中的图片格式五花八门吧&#xff0c;我常常分不清各种格式的使用场景和区别&#xff0c;有些常见的格式和很少见的&#xff0c;在此总结。 常见格式 常见的图片格式&#xff0c;有 JPEG、PNG、GIF、BMP、WebP、SVG、TIFF、ICO等&#xff0c; 少见的比如&#xff1a;HD…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...