格豪网络建站/数据平台
一、题目描述
给定 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 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 示例 1: 输入:heights [2,1,5,6,2,3] 输出:10 解释:…...

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

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,同时在本地提交任务。 主要参考了官方文档: Farm Queue — Omniverse Farm latest documentation Farm Agent — Omniverse Farm latest documentation Farm Examples — Omniverse Far…...

第28关 k8s监控实战之Prometheus(二)
------> 课程视频同步分享在今日头条和B站 大家好,我是博哥爱运维。 这节课我们用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 是一个前后端分离后台管理系统, 前端集成 amis 低代码前端框架,后端集成 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. 最长递增子序列 题目链接:最长递增子序列 dp数组及下标的含义 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度递推公式 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] > nums[j]) dp[i]…...

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

代码随想录刷题题Day29
刷题的第二十九天,希望自己能够不断坚持下去,迎来蜕变。😀😀😀 刷题语言:C Day29 任务 ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 …...

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

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

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

SpringBoot+Redis实现接口防刷功能
场景描述: 在实际开发中,当前端请求后台时,如果后端处理比较慢,但是用户是不知情的,此时后端仍在处理,但是前端用户以为没点到,那么再次点击又发起请求,就会导致在短时间内有很多请求…...

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

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

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

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

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

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

SpringMVC通用后台管理系统源码
整体的SSM后台管理框架功能已经初具雏形,前端界面风格采用了结构简单、 性能优良、页面美观大的Layui页面展示框架 数据库支持了SQLserver,只需修改配置文件即可实现数据库之间的转换。 系统工具中加入了定时任务管理和cron生成器,轻松实现系统调度问…...

深度解析Dubbo的基本应用与高级应用:负载均衡、服务超时、集群容错、服务降级、本地存根、本地伪装、参数回调等关键技术详解
负载均衡 官网地址: http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略, 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的? 讲道理, 最少活跃数…...

备战2024美赛数学建模,文末获取历史优秀论文
总说(历年美赛优秀论文可获取) 数模的题型千变万化,我今天想讲的主要是一些「画图」、「建模」、「写作」和「论文结构」的思路,这些往往是美赛阅卷官最看重的点,突破了这些点,才能真正让你的美赛论文更上…...

Java加密解密大全(MD5、RSA)
目录 一、MD5加密二、RSA加解密(公加私解,私加公解)三、RSA私钥加密四、RSA私钥加密PKCS1Padding模式 一、MD5加密 密文形式:5eb63bbbe01eeed093cb22bb8f5acdc3 import java.math.BigInteger; import java.security.MessageDigest; import java.security…...

C语言程序设计考试掌握这些题妥妥拿绩点(写给即将C语言考试的小猿猴们)
目录 开篇说两句1. 水仙花数题目描述分析代码示例 2. 斐波那契数列题目描述分析代码示例 3. 猴子吃桃问题题目描述分析代码示例 4. 物体自由落地题目描述分析代码示例 5. 矩阵对角线元素之和题目描述分析代码示例 6. 求素数题目描述分析代码示例 7. 最大公约数和最小公倍数题目…...

编译ZLMediaKit(win10+msvc2019_x64)
前言 因工作需要,需要ZLMediaKit,为方便抓包分析,最好在windows系统上测试,但使用自己编译的第三方库一直出问题,无法编译通过。本文档记录下win10上的编译过程,供有需要的小伙伴使用 一、需要安装的软件…...

JS-基础语法(一)
JavaScript简单介绍 变量 常量 数据类型 类型转换 案例 1.JavaScript简单介绍 JavaScript 是什么? 是一种运行在客户端(浏览器)的编程语言,可以实现人机交互效果。 JS的作用 JavaScript的组成 JSECMAScript( 基础语法 )…...

18款Visual Studio实用插件(更新)
前言 俗话说的好工欲善其事必先利其器,安装一些Visual Studio实用插件对自己日常的开发和工作效率能够大大的提升,避免996从选一款好的IDE实用插件开始。以下是我认为比较实用的Visual Studio插件希望对大家有用,大家有更好的插件推荐可在文…...

三、java线性表(顺序表、链表、栈、队列)
java线性表 三、线性表1.1 顺序表1.2 链表1.2.1 单向链表(Singly Linked List)1.2.2 双向链表(Doubly Linked List) 1.3 LinkedList VS ArrayList1.3.7 使用 LinkedList 的场景 1.4 栈1.5 队列 三、线性表 线性表是一种经典的数据…...

PiflowX-MysqlCdc组件
MysqlCdc组件 组件说明 MySQL CDC连接器允许从MySQL数据库读取快照数据和增量数据。 计算引擎 flink 组件分组 cdc 端口 Inport:默认端口 outport:默认端口 组件属性 名称展示名称默认值允许值是否必填描述例子hostnameHostname“”无是MySQL…...