当前位置: 首页 > 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…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...