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

LeetCode 84:柱状图中的最大矩形

一、题目描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

输入: heights = [2,4]
输出: 4

提示:

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

二、思路分析

使用栈空间来解决本题,通过空间换时间的方式。

三、代码参考

1、Java

class Solution {public int largestRectangleArea(int[] heights) {// 获取数组长度int len = heights.length;// 数组长度为 0 或者 1 时直接返回if(len == 0){return 0;}if(len == 1){return heights[0];}// 用来返回最大面积,初始值为 0int area = 0;// 创建栈空间做辅助Deque<Integer> stack = new ArrayDeque<>();// 循环遍历数组for(int i = 0; i < len; i++){// while(!stack.isEmpty() && heights[stack.peekLast()] > heights[i]){// 获取栈顶高度,并移除当前栈顶int height = heights[stack.removeLast()];// 做特殊的处理,如果当前栈顶的高度和上一个栈顶的高度相同,则也需要进行弹栈while(!stack.isEmpty() && heights[stack.peekLast()] == height){// 移除栈顶元素stack.removeLast();}// 创建宽度变量,初始值为 0int width = 0;// 如果栈为空,说明,有效柱体能够从 i 的左边一直延伸到第一个开始if(stack.isEmpty()){// 所以此时的宽度为 iwidth = i;}else {width = i - stack.peekLast() - 1;}// 计算面积, 长 * 宽,并获取最大面积area = Math.max(area, height * width);}// 将下标存入栈空间中stack.addLast(i);}// 将当前栈中的所有元素弹出while(!stack.isEmpty()){// 获取栈顶高度,并移除当前栈顶int height = heights[stack.removeLast()];// 做特殊的处理,如果当前栈顶的高度和上一个栈顶的高度相同,则也需要进行弹栈while(!stack.isEmpty() && heights[stack.peekLast()] == height){// 移除栈顶元素stack.removeLast();}// 创建宽度变量,初始值为 0int width = 0;// 如果栈为空,说明,有效柱体能够从 i 的左边一直延伸到第一个开始if(stack.isEmpty()){// 所以此时的宽度为 lenwidth = len;}else {width = len - stack.peekLast() - 1;}// 计算面积, 长 * 宽,并获取最大面积area = Math.max(area, height * width);}// 返回面积结果return area;}
}

2、Python

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:size = len(heights)area = 0stack = []for i in range(size):while len(stack) > 0 and heights[i] < heights[stack[-1]]:height = heights[stack.pop()]while len(stack) > 0 and height == heights[stack[-1]]:stack.pop()if len(stack) > 0:width = i - stack[-1] - 1else:width = iarea = max(area, height * width)stack.append(i)while len(stack) > 0 is not None:height = heights[stack.pop()]while len(stack) > 0 and height == heights[stack[-1]]:stack.pop()if len(stack) > 0:width = size - stack[-1] - 1else:width = sizearea = max(area, height * width)return area

相关文章:

LeetCode 84:柱状图中的最大矩形

一、题目描述 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 示例 1: 输入&#xff1a;heights [2,1,5,6,2,3] 输出&#xff1a;10 解释&#xff1a…...

老生重谈:大模型的「幻觉」问题

一、什么是大模型「幻觉」 大模型的幻觉问题通常指的是模型在处理输入时可能会产生一些看似合理但实际上是错误的输出&#xff0c;这可能是因为模型在训练时过度拟合了训练数据&#xff0c;导致对噪声或特定样本的过度敏感。 "大数据幻觉"指的是在处理大规模数据时…...

golang实现skiplist 跳表

跳表 package mainimport ("errors""math""math/rand" )func main() {// 双向链表///**先理解查找过程Level 3: 1 6Level 2: 1 3 6Level 1: 1 2 3 4 6比如 查找2 ; 从高层往下找;如果查找的值比当前值小 说明没有可查找的值2比1大 往当前…...

尝试OmniverseFarm的最基础操作

目标 尝试OmniverseFarm的最基础操作。本地机器作为Queue和Agent&#xff0c;同时在本地提交任务。 主要参考了官方文档&#xff1a; Farm Queue — Omniverse Farm latest documentation Farm Agent — Omniverse Farm latest documentation Farm Examples — Omniverse Far…...

第28关 k8s监控实战之Prometheus(二)

------> 课程视频同步分享在今日头条和B站 大家好&#xff0c;我是博哥爱运维。 这节课我们用prometheus-operator来安装整套prometheus服务 https://github.com/prometheus-operator/kube-prometheus/releases 开始安装 1. 解压下载的代码包 wget https://github.com/…...

基于 SpringBoot + magic-api + Vue3 + Element Plus + amis3.0 快速开发管理系统

Tansci-Boot 基于 SpringBoot2 magic-api Vue3 Element Plus amis3.0 快速开发管理系统 Tansci-Boot 是一个前后端分离后台管理系统&#xff0c; 前端集成 amis 低代码前端框架&#xff0c;后端集成 magic-api 的接口快速开发框架。包含基础权限、安全认证、以及常用的一…...

Kafka(四)Broker

目录 1 配置Broker1.1 Broker的配置broker.id0listererszookeeper.connectlog.dirslog.dir/tmp/kafka-logsnum.recovery.threads.per.data.dir1auto.create.topics.enabletrueauto.leader.rebalance.enabletrue, leader.imbalance.check.interval.seconds300, leader.imbalance…...

代码随想录第五十二天——最长递增子序列,最长连续递增序列,最长重复子数组

leetcode 300. 最长递增子序列 题目链接&#xff1a;最长递增子序列 dp数组及下标的含义 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度递推公式 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] > nums[j]) dp[i]…...

【大数据架构】OLAP实时分析引擎选型

OLAP引擎面临的挑战 常见OLAP引擎对比 OLAP分析场景中&#xff0c;一般认为QPS达到1000就算高并发&#xff0c;而不是像电商、抢红包等业务场景中&#xff0c;10W以上才算高并发&#xff0c;毕竟数据分析场景&#xff0c;数据海量&#xff0c;计算复杂&#xff0c;QPS能够达到1…...

代码随想录刷题题Day29

刷题的第二十九天&#xff0c;希望自己能够不断坚持下去&#xff0c;迎来蜕变。&#x1f600;&#x1f600;&#x1f600; 刷题语言&#xff1a;C Day29 任务 ● 01背包问题&#xff0c;你该了解这些&#xff01; ● 01背包问题&#xff0c;你该了解这些&#xff01; 滚动数组 …...

CVE-2023-51385 OpenSSH ProxyCommand命令注入漏洞

一、背景介绍 ProxyCommand 是 OpenSSH ssh_config 文件中的一个配置选项&#xff0c;它允许通过代理服务器建立 SSH 连接&#xff0c;从而在没有直接网络访问权限的情况下访问目标服务器。这对于需要经过跳板机、堡垒机或代理服务器才能访问的目标主机非常有用。 二、漏洞简…...

如何寻找到相对完整的真正的游戏的源码 用来学习?

在游戏开发的学习之路上&#xff0c;理论与实践是并重的两个方面。对于许多热衷于游戏开发的学习者来说&#xff0c;能够接触到真实的、完整的游戏源码无疑是一个极好的学习机会。但问题来了&#xff1a;我们该如何寻找到这些珍贵的资源呢&#xff1f; 开源游戏项目 GitHub:地…...

数模学习day11-系统聚类法

本文参考辽宁石油化工大学于晶贤教授的演示文档聚类分析之系统聚类法及其SPSS实现。 目录 1.样品与样品间的距离 2.指标和指标间的“距离” 相关系数 夹角余弦 3.类与类间的距离 &#xff08;1&#xff09;类间距离 &#xff08;2&#xff09;类间距离定义方式 1.最短…...

SpringBoot+Redis实现接口防刷功能

场景描述&#xff1a; 在实际开发中&#xff0c;当前端请求后台时&#xff0c;如果后端处理比较慢&#xff0c;但是用户是不知情的&#xff0c;此时后端仍在处理&#xff0c;但是前端用户以为没点到&#xff0c;那么再次点击又发起请求&#xff0c;就会导致在短时间内有很多请求…...

TensorRT加速推理入门-1:Pytorch转ONNX

这篇文章&#xff0c;用于记录将TransReID的pytorch模型转换为onnx的学习过程&#xff0c;期间参考和学习了许多大佬编写的博客&#xff0c;在参考文章这一章节中都已列出&#xff0c;非常感谢。 1. 在pytorch下使用ONNX主要步骤 1.1. 环境准备 安装onnxruntime包 安装教程可…...

springboot常用扩展点

当涉及到Spring Boot的扩展和自定义时&#xff0c;Spring Boot提供了一些扩展点&#xff0c;使开发人员可以根据自己的需求轻松地扩展和定制Spring Boot的行为。本篇博客将介绍几个常用的Spring Boot扩展点&#xff0c;并提供相应的代码示例。 1. 自定义Starter(面试常问) Sp…...

19道ElasticSearch面试题(很全)

点击下载《19道ElasticSearch面试题&#xff08;很全&#xff09;》 1. elasticsearch的一些调优手段 1、设计阶段调优 &#xff08;1&#xff09;根据业务增量需求&#xff0c;采取基于日期模板创建索引&#xff0c;通过 roll over API 滚动索引&#xff1b; &#xff08;…...

向爬虫而生---Redis 拓宽篇3 <GEO模块>

前言: 继上一章: 向爬虫而生---Redis 拓宽篇2 &#xff1c;Pub/Sub发布订阅&#xff1e;-CSDN博客 这一章的用处其实不是特别大,主要是针对一些地图和距离业务的;就是Redis的GEO模块。 GEO模块是Redis提供的一种高效的地理位置数据管理方案&#xff0c;它允许我们存储和查询…...

Vue项目里实现json对象转formData数据

平常调用后端接口传参都是json对象&#xff0c;当提交表单遇到有附件需要传递时&#xff0c;通常是把附件上传单独做个接口&#xff0c;也有遇到后端让提交接口一并把附件传递到后端&#xff0c;这种情况需要把参数转成formData的数据&#xff0c;需要用到new FormData()。json…...

leetcode刷题记录

栈 2696. 删除子串后的字符串最小长度 哈希表 1. 两数之和 用map来保存每个数和他的索引 383. 赎金信 用map来存储字符的个数 链表 2. 两数相加 指针的移动 动态规划 53. 最大子数组和 2707. 字符串中的额外字符 递归 101. 对称二叉树 数学 1276. 不浪费原料的汉堡…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...