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

代码随想录算法训练营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. 柱状图中最大的矩形 - 力扣&#xff08;LeetCode&#xff09; 题目 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图…...

Modbus TCP转Profibus DP网关modbus tcp报文解析

捷米JM-DPM-TCP网关。在Profibus总线侧作为主站&#xff0c;在以太网侧作为ModbusTcp服务器功能&#xff0c; 下面是介绍捷米JM-DPM-TCP主站网关组态工具的配置方法 2, Profibus主站组态工具安装 执行资料光盘中的安装文件setup64.exe或setup.exe安装组态工具。安装过程中一直…...

对 Promise 的理解

Promise 是异步编程的一种解决方案&#xff0c;它是一个对象&#xff0c;可以获取异步 操作的消息&#xff0c;他的出现大大改善了异步编程的困境&#xff0c;避免了地狱回调&#xff0c; 它比传统的解决方案回调函数和事件更合理和更强大。 所谓 Promise&#xff0c;简单说就…...

Vuex:Vue.js应用程序的状态管理模式

介绍 在Vue.js应用程序中&#xff0c;随着项目复杂度的增加&#xff0c;组件之间的数据共享和管理变得困难。为了解决这个问题&#xff0c;Vue.js提供了一个名为Vuex的状态管理模式。Vuex可以帮助我们更有效地组织、管理和共享应用程序的状态。 什么是Vuex&#xff1f; Vuex…...

Unity之ShaderGraph 节点介绍 Utility节点

Utility 逻辑All&#xff08;所有分量都不为零&#xff0c;返回 true&#xff09;Any&#xff08;任何分量不为零&#xff0c;返回 true&#xff09;And&#xff08;A 和 B 均为 true&#xff09;Branch&#xff08;动态分支&#xff09;Comparison&#xff08;两个输入值 A 和…...

springboot()—— swagger

零、一张图读懂swagger 懂了&#xff0c;这玩意就是用swagger搞出来的&#xff01; 就是一个后端开发自测的东西嘛&#xff01; 一、概念 存在即合理&#xff0c;我们看一下swagger诞生的原因&#xff1a;在前后端分离的架构中&#xff0c;前端新增一个字段&#xff0c;后端就…...

Java课题笔记~ 关联映射

一、MyBatis关联查询 在关系型数据库中&#xff0c;表与表之间存在着3种关联映射关系&#xff0c;分别为一对一、一对多、多对多。 一对一&#xff1a;一个数据表中的一条记录最多可以与另一个数据表中的一条记录相关。列如学生与学号就属于一对一关系。 一对多&#xff1a;主…...

一零六七、JVM梳理

JVM&#xff1f; Java虚拟机&#xff0c;可以理解为Java程序的运行环境&#xff0c;可以执行Java字节码&#xff08;Java bytecode&#xff09;并提供了内存管理、垃圾回收、线程管理等功能 java内存区域划分?每块内存中都对应什么? 方法区&#xff1a;类的结构信息、常量池、…...

【CSS】网格布局(简单布局、网格合并、网格嵌套)

文章目录 CSS网格布局&#xff08;Grid Layout&#xff09;1. 简单布局2. 网格合并3. 网格嵌套4. 总结 CSS网格布局&#xff08;Grid Layout&#xff09; CSS网格布局&#xff08;Grid Layout&#xff09;是一种强大且灵活的CSS布局系统&#xff0c;允许开发者以网格形式组织和…...

06 Ubuntu22.04上的miniconda3安装、深度学习常用环境配置

下载脚本 我依然是在清华镜像当中寻找的脚本。这里找脚本真的十分方便&#xff0c;我十分推荐。 wget https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/Miniconda3-latest-Linux-x86_64.sh 下载十分快速&#xff0c;10秒解决问题 运行miniconda3安装脚本 赋予执…...

【CSS3】CSS3 动画 ② ( 动画序列 | 使用 from 和 to 定义动画序列 | 定义多个动画节点 | 代码示例 )

文章目录 一、动画序列二、代码示例 - 使用 from 和 to 定义动画序列三、代码示例 - 定义多个动画节点 一、动画序列 定义动画时 , 需要设置动画序列 , 下面的 0% 和 100% 设置的是 动画 在 运行到某个 百分比节点时 的 标签元素样式状态 ; keyframes element-move { 0% { tr…...

最优化:建模、算法与理论

最优化&#xff1a;建模、算法与理论 目前在学习 最优化&#xff1a;建模、算法与理论这本书&#xff0c;来此记录一下&#xff0c;顺便做一些笔记&#xff0c;在其中我也会加一些自己的理解&#xff0c;尽量写的不会那么的条条框框&#xff08;当然最基础的还是要有&#xff…...

拿捏--->打印菱形

文章目录 题目描述算法思路代码示例 题目描述 在屏幕上输出以下图案&#xff1a; 算法思路 代码示例 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() {int n;scanf("%d", &n);//上半部分菱形for (int i 0; i < n; i) //上半部分…...

【SpringBoot笔记】定时任务(cron)

定时任务就是在固定的时间执行某个程序&#xff0c;闹钟的作用。 1.在启动类上添加注解 EnableScheduling 2.创建定时任务类 在这个类里面使用表达式设置什么时候执行 cron 表达式&#xff08;也叫七子表达式&#xff09;&#xff0c;设置执行规则 package com.Lijibai.s…...

Redis单机,主从,哨兵,集群四大模式

Redis 单机模式 Redis 单机模式是指 Redis 数据库在单个服务器上以独立的、单一的进程运行的模式。在这种模式下&#xff0c;Redis 不涉及数据分片或集群配置&#xff0c;所有的数据和操作都在一个实例中进行。以下是关于 Redis 单机模式的详细介绍&#xff1a; 单一实例&#…...

2023年8月份华为H12-811更新了

801、[单选题]178/832、在系统视图下键入什么命令可以切换到用户视图? A quit B souter C system-view D user-view 试题答案&#xff1a;A 试题解析&#xff1a;在系统视图下键入quit命令退出到用户视图。因此答案选A。 802、[单选题]“网络管理员在三层交换机上创建了V…...

[K8S:命令执行:权限异常:解决篇]:通过更新kubeconfig配置相关信息

文章目录 一&#xff1a;场景复现&#xff1a;1.1&#xff1a;关键信息&#xff1a;1.2&#xff1a;全异常日志输出&#xff1a; 二&#xff1a;解决流程&#xff1a;2.1&#xff1a;更新 kubeconfig&#xff1a;2.1.1&#xff1a;执行命令&#xff1a; 2.2&#xff1a;再次执行…...

帆软设计器报表加载不出折线图的原因

最近在用帆软设计器做可视化图表。偶有遇到因为数据集的字段类型导致加载不出折线&#xff0c;现记录如下。做报表的同行可以参考。 数据库使用了 Oracle 11g。数据集的 SQL 代码片是之前用在另一个单元格报表里面的。页面上有一个率是直接计算得出&#xff0c;我为了方便、就…...

[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请求的不同发送方式

&#x1f954;&#xff1a;你一定能成为想要成为的人 发送AJAX请求不同方式 发送AJAX请求不同方式1、jQuery发送AJAX请求2、axios发送AJAX请求&#xff08;重点&#xff09;3、fetch发送AJAX请求 发送AJAX请求不同方式 1、jQuery发送AJAX请求 首先需要jquery的js文件&#xf…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...