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

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...