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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...