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

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

【HTTP三个基础问题】

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

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...