代码随想录算法训练营day60
文章目录
- Day60
- 柱状图中最大的矩形
- 题目
- 思路
- 代码
Day60
柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣(LeetCode)
题目
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。

思路
本题和42. 接雨水 (opens new window),是遥相呼应的两道题目
接雨水要查找的是右边第一个比元素大的值进行计算,所以使用了递增单调栈(从栈口到栈底)
本题要查找的是右边第一个比元素小的值进行计算,所以使用了递减单调栈(从栈口到栈底)
本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序!
栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
理解这一点,对单调栈就掌握的比较到位了。
除了栈内元素顺序和接雨水不同,剩下的逻辑就都差不多了,在题解42. 接雨水 (opens new window)我已经对单调栈的各个方面做了详细讲解,这里就不赘述了。
主要就是分析清楚如下三种情况:
- 情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
- 情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
- 情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
细节:
末尾为什么要加元素0?
如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果的哪一步,所以最后输出的就是0了。 如图:

那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑。
开头为什么要加元素0?
如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left。
(mid、left,right 都是对应版本一里的逻辑)
因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。
之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果resutl就是0。 如图所示:

代码
class Solution {public int largestRectangleArea(int[] heights) {int newHeights[] = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for(int i = 0; i < heights.length; i++) newHeights[i + 1] = heights[i];LinkedList<Integer> stack = new LinkedList<>();stack.push(0);int sum = 0;for(int i = 1; i < newHeights.length; i++){int position = stack.peek();if(newHeights[i] > newHeights[position]){stack.push(i);}else if(newHeights[i] == newHeights[position]){// 这里可以不做操作stack.pop();stack.push(i);}else{while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]){int mid = stack.peek();stack.pop();if(!stack.isEmpty()){int left = stack.peek();int right = i;int w = right - left - 1;int h = newHeights[mid];sum = Math.max(sum, w * h);}}stack.push(i);}}return sum;}
}
相关文章:
代码随想录算法训练营day60
文章目录 Day60 柱状图中最大的矩形题目思路代码 Day60 柱状图中最大的矩形 84. 柱状图中最大的矩形 - 力扣(LeetCode) 题目 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图…...
Modbus TCP转Profibus DP网关modbus tcp报文解析
捷米JM-DPM-TCP网关。在Profibus总线侧作为主站,在以太网侧作为ModbusTcp服务器功能, 下面是介绍捷米JM-DPM-TCP主站网关组态工具的配置方法 2, Profibus主站组态工具安装 执行资料光盘中的安装文件setup64.exe或setup.exe安装组态工具。安装过程中一直…...
对 Promise 的理解
Promise 是异步编程的一种解决方案,它是一个对象,可以获取异步 操作的消息,他的出现大大改善了异步编程的困境,避免了地狱回调, 它比传统的解决方案回调函数和事件更合理和更强大。 所谓 Promise,简单说就…...
Vuex:Vue.js应用程序的状态管理模式
介绍 在Vue.js应用程序中,随着项目复杂度的增加,组件之间的数据共享和管理变得困难。为了解决这个问题,Vue.js提供了一个名为Vuex的状态管理模式。Vuex可以帮助我们更有效地组织、管理和共享应用程序的状态。 什么是Vuex? Vuex…...
Unity之ShaderGraph 节点介绍 Utility节点
Utility 逻辑All(所有分量都不为零,返回 true)Any(任何分量不为零,返回 true)And(A 和 B 均为 true)Branch(动态分支)Comparison(两个输入值 A 和…...
springboot()—— swagger
零、一张图读懂swagger 懂了,这玩意就是用swagger搞出来的! 就是一个后端开发自测的东西嘛! 一、概念 存在即合理,我们看一下swagger诞生的原因:在前后端分离的架构中,前端新增一个字段,后端就…...
Java课题笔记~ 关联映射
一、MyBatis关联查询 在关系型数据库中,表与表之间存在着3种关联映射关系,分别为一对一、一对多、多对多。 一对一:一个数据表中的一条记录最多可以与另一个数据表中的一条记录相关。列如学生与学号就属于一对一关系。 一对多:主…...
一零六七、JVM梳理
JVM? Java虚拟机,可以理解为Java程序的运行环境,可以执行Java字节码(Java bytecode)并提供了内存管理、垃圾回收、线程管理等功能 java内存区域划分?每块内存中都对应什么? 方法区:类的结构信息、常量池、…...
【CSS】网格布局(简单布局、网格合并、网格嵌套)
文章目录 CSS网格布局(Grid Layout)1. 简单布局2. 网格合并3. 网格嵌套4. 总结 CSS网格布局(Grid Layout) CSS网格布局(Grid Layout)是一种强大且灵活的CSS布局系统,允许开发者以网格形式组织和…...
06 Ubuntu22.04上的miniconda3安装、深度学习常用环境配置
下载脚本 我依然是在清华镜像当中寻找的脚本。这里找脚本真的十分方便,我十分推荐。 wget https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/Miniconda3-latest-Linux-x86_64.sh 下载十分快速,10秒解决问题 运行miniconda3安装脚本 赋予执…...
【CSS3】CSS3 动画 ② ( 动画序列 | 使用 from 和 to 定义动画序列 | 定义多个动画节点 | 代码示例 )
文章目录 一、动画序列二、代码示例 - 使用 from 和 to 定义动画序列三、代码示例 - 定义多个动画节点 一、动画序列 定义动画时 , 需要设置动画序列 , 下面的 0% 和 100% 设置的是 动画 在 运行到某个 百分比节点时 的 标签元素样式状态 ; keyframes element-move { 0% { tr…...
最优化:建模、算法与理论
最优化:建模、算法与理论 目前在学习 最优化:建模、算法与理论这本书,来此记录一下,顺便做一些笔记,在其中我也会加一些自己的理解,尽量写的不会那么的条条框框(当然最基础的还是要有ÿ…...
拿捏--->打印菱形
文章目录 题目描述算法思路代码示例 题目描述 在屏幕上输出以下图案: 算法思路 代码示例 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() {int n;scanf("%d", &n);//上半部分菱形for (int i 0; i < n; i) //上半部分…...
【SpringBoot笔记】定时任务(cron)
定时任务就是在固定的时间执行某个程序,闹钟的作用。 1.在启动类上添加注解 EnableScheduling 2.创建定时任务类 在这个类里面使用表达式设置什么时候执行 cron 表达式(也叫七子表达式),设置执行规则 package com.Lijibai.s…...
Redis单机,主从,哨兵,集群四大模式
Redis 单机模式 Redis 单机模式是指 Redis 数据库在单个服务器上以独立的、单一的进程运行的模式。在这种模式下,Redis 不涉及数据分片或集群配置,所有的数据和操作都在一个实例中进行。以下是关于 Redis 单机模式的详细介绍: 单一实例&#…...
2023年8月份华为H12-811更新了
801、[单选题]178/832、在系统视图下键入什么命令可以切换到用户视图? A quit B souter C system-view D user-view 试题答案:A 试题解析:在系统视图下键入quit命令退出到用户视图。因此答案选A。 802、[单选题]“网络管理员在三层交换机上创建了V…...
[K8S:命令执行:权限异常:解决篇]:通过更新kubeconfig配置相关信息
文章目录 一:场景复现:1.1:关键信息:1.2:全异常日志输出: 二:解决流程:2.1:更新 kubeconfig:2.1.1:执行命令: 2.2:再次执行…...
帆软设计器报表加载不出折线图的原因
最近在用帆软设计器做可视化图表。偶有遇到因为数据集的字段类型导致加载不出折线,现记录如下。做报表的同行可以参考。 数据库使用了 Oracle 11g。数据集的 SQL 代码片是之前用在另一个单元格报表里面的。页面上有一个率是直接计算得出,我为了方便、就…...
[QCA6174]sdx12平台WiFi QCA6174在驱动加载的时候增加模块参数方法
需求描述 由于开发需要,有时候需要在驱动模块加载的时候增加一个参数,传递给到驱动使用 平台描述 Qualcomm SDX12+QCA6174平台 驱动信息 [ 112.281429] wlan: loading driver v4.0.11.213X [ 112.340262] msm_pcie_enable: PCIe: Assert the reset of endpoint of RC0. …...
Ajax-AJAX请求的不同发送方式
🥔:你一定能成为想要成为的人 发送AJAX请求不同方式 发送AJAX请求不同方式1、jQuery发送AJAX请求2、axios发送AJAX请求(重点)3、fetch发送AJAX请求 发送AJAX请求不同方式 1、jQuery发送AJAX请求 首先需要jquery的js文件…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
