当前位置: 首页 > 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…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

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

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

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...