代码随想录打卡第六十三天|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.柱状图中最大的矩形 题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 提示: 1 < heights.length <105 0 < h…...
python tempfile 模块使用
在Python中,tempfile 模块用于创建临时文件和目录,它们可以用于存储中间处理数据,不需要长期保存。该模块提供了几种不同的类和函数来创建临时文件和目录。 下面是几个常用的 tempfile 使用方法: 临时文件 使用 NamedTemporary…...
【软件测试】接口测试实战详解
最近找到了几个问题,都还比较有代表性。 作为一个初级测试,想学接口测试,但是一点头绪都没有。求教大神指点,有没有好的书或者工具推荐?如何做接口测试呢?接口测试有哪些工具做接口测试的流程一般是怎么样…...
轻量封装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点击安装,注意以下步骤 本文设置nodejs的安装的路径:D:\soft\nodejs 继续点击next,选中Add to PATH ,旁边的英文告诉我们会把 环境变量 给我们配置好 当然也可以只选择 Nod…...
03【保姆级】-GO语言变量和数据类型和相互转换
03【保姆级】-GO语言变量和数据类型 一、变量1.1 变量的定义: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 在线官网: https://mermaid-js.github.io/ 在线学习文件: https://mermaid.js.org/syntax/quadrantChart.html 1、今天主要是想做需求解释的流程图,又不想自己画,就用了,框框不能直接进行全局配置࿰…...
SAP MASS增加PR字段-删除标识
MASS->BUS2105->发现没有找到PR删除标识字段 SAP MASS增加PR字段-删除标识 1.tcode:MASSOBJ 选中BUS2105 点“应用程序表” 点“字段列表” 2.选中一行进行参考 3.修改字段为删除标识 LOEKZ,保存即可。 4.然后MASS操作,批量设置删除标识&…...
【手把手教你】训练YOLOv8分割模型
1.下载文件 在github上下载YOLOV8模型的文件,搜索yolov8,star最多这个就是 2. 准备环境 环境要求python>3.8,PyTorch>1.8,自行安装ptyorch环境即可 2. 制作数据集 制作数据集,需要使用labelme这个包&#…...
物料主数据增强屏幕绘制器DUMP
问题描述 在做完物料主数据增强后,配置和代码传Q,在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 注意:引入luckysheet,只能通过CDN或者直接引入静态资源的形式,不能npm install。 个人建议直接下载资源引入。我给你们提供一个下载资源的地址: …...
AIGPT重大升级,界面重新设计,功能更加饱满,用户体验升级
AIGPT AIGPT是一款功能强大的人工智能技术处理软件,不但拥有其他模型处理文本认知的能力还有AI绘画模型、拥有自身的插件库。 我们都知道使用ChatGPT是需要账号以及使用魔法的,实现其中的某一项对我们一般的初学者来说都是一次巨大的挑战,但…...
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 之后, 在查找用户手机是否有安装app,进行查询包名是否存在时,getPackageManager().getPackageInfo()这个函数一直返回null ,Android 11增加了权限要求。 1、只是查询指定的App 包 只需要在Andro…...
4、数据结构
数据结构01 数值处理 取整 日常用的四种 / 整数除法,截取整数部分math.Ceil 向上取整 “理解为天花板,向上取值”math.Floor 向下取整 “理解为地板,向下取值”math.Round 四舍五入 / 整数除法,截取整数部分 func main() { f…...
qt5.15.2+vs2019源码调试开发环境搭建
说明 一些qt文件不进行源码调试无法知道其中的原理。提高软件质量,从概念原理及应用角度看待必须知道qt类运行原理。 1.安装 在网上找到qt安装包qt-unified-windows-x64-4.5.1-online.exe,安装qt5.15.2,有选择Qt Debug Information Files …...
【数据结构】单链表之--无头单向非循环链表
前言:前面我们学习了动态顺序表并且模拟了它的实现,今天我们来进一步学习,来学习单链表!一起加油各位,后面的路只会越来越难走需要我们一步一个脚印! 💖 博主CSDN主页:卫卫卫的个人主页 &#x…...
网络中使用最多的图片格式有哪些
互联网中的图片格式五花八门吧,我常常分不清各种格式的使用场景和区别,有些常见的格式和很少见的,在此总结。 常见格式 常见的图片格式,有 JPEG、PNG、GIF、BMP、WebP、SVG、TIFF、ICO等, 少见的比如:HD…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
