当前位置: 首页 > 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. 不浪费原料的汉堡…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...