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

代码随想录-刷题第五十七天

42. 接雨水

题目链接:42. 接雨水

思路:本题十分经典,使用单调栈需要理解的几个问题:

  1. 首先单调栈是按照行方向来计算雨水,如图:

    42.接雨水2

  2. 使用单调栈内元素的顺序

    从大到小还是从小到大呢?

    从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。

    因为一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。

    如图:

    42.接雨水4

    关于单调栈的顺序:739. 每日温度中求一个元素右边第一个更大元素,单调栈就是递增的,84.柱状图中最大的矩形求一个元素右边第一个更小元素,单调栈就是递减的。

  3. 遇到相同高度的柱子怎么办。

    遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中,需要使用最右边的柱子来计算宽度

  4. 栈里要保存什么数值

    栈里就存放下标就行,想要知道对应的高度,通过height[stack.peek()] 就知道弹出的下标对应的高度了。

class Solution {public int trap(int[] height) {// 找每个柱子左右两边第一个大于该柱子高度的柱子int res = 0;Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < height.length; i++) {if (height[i] < height[stack.peek()]) {// 情况一stack.push(i);} else if (height[i] == height[stack.peek()]) {// 情况二stack.pop();stack.push(i);} else {// 情况三while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.pop(); // 凹槽的底部,也就是中间位置if (!stack.isEmpty()) {int left = stack.peek();int h = Math.min(height[left], height[i]) - height[mid];int w = i - left - 1; // 注意减一,只求中间宽度res += h * w;}}stack.push(i);}}return res;}
}

双指针解法如下:

class Solution {public int trap(int[] height) {int n = height.length;int res = 0;// 数组充当备忘录int[] l_max = new int[n];int[] r_max = new int[n];// 初始化 base casel_max[0] = height[0];r_max[n - 1] = height[n - 1];// 从左向右计算 l_maxfor (int i = 1; i < n; i++)l_max[i] = Math.max(height[i], l_max[i - 1]);// 从右向左计算 r_maxfor (int i = n - 2; i >= 0; i--)r_max[i] = Math.max(height[i], r_max[i + 1]);// 计算答案for (int i = 1; i < n - 1; i++)res += Math.min(l_max[i], r_max[i]) - height[i];return res;}
}

为了得到两边的最高高度,使用了双指针来遍历,每到一个柱子都向两边遍历一遍,这其实是有重复计算的。把每一个位置的左边最高高度记录在一个数组上(l_max),右边最高高度记录在一个数组上(r_max),这样就避免了重复计算。


84. 柱状图中最大的矩形

题目链接:84. 柱状图中最大的矩形

思路:本题十分适合与接雨水对照来看,接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子高度的柱子。

本题与接雨水最主要的区别在于单调栈中存放元素的顺序不同。其他步骤与接雨水的分析过程相同。

只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。(栈顶和栈顶的下一个元素以及要入栈的三个元素组成了要求最大面积的高度和宽度

class Solution {public int largestRectangleArea(int[] heights) {// 找每个柱子左右两边第一个小于该柱子高度的柱子int res = 0;Deque<Integer> stack = new LinkedList<>();// 数组前后各加一个0int[] 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];}stack.push(0);// 开始遍历for (int i = 1; i < newHeights.length; i++) {if (newHeights[i] > newHeights[stack.peek()]) {// 情况一stack.push(i);} else if (newHeights[i] == newHeights[stack.peek()]) {// 情况二stack.pop();stack.push(i);} else {// 情况三while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {int mid = stack.pop();if (!stack.isEmpty()) {int left = stack.peek();int h = newHeights[mid];int w = i - left - 1;res = Math.max(res, h * w);}}stack.push(i);}}return res;}
}

在 height数组上后,都加了一个元素0, 为什么这么做呢?

首先来说末尾为什么要加元素0?

如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果的哪一步,所以最后输出的就是0了。

开头为什么要加元素0?

如果数组本身降序,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时得到 mid(8),right(6),但是得不到 left。因为将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。之后又将6 加入栈(此时8已经弹出了),然后就是 4 与栈口元素 8 进行比较,周而复始,那么计算的最后结果result就是0。


相关文章:

代码随想录-刷题第五十七天

42. 接雨水 题目链接&#xff1a;42. 接雨水 思路&#xff1a;本题十分经典&#xff0c;使用单调栈需要理解的几个问题&#xff1a; 首先单调栈是按照行方向来计算雨水&#xff0c;如图&#xff1a; 使用单调栈内元素的顺序 从大到小还是从小到大呢&#xff1f; 从栈头&…...

flutter 播放SVGA动图

SVGAPlayer-Flutter&#xff1a;这是一个轻量级的动画渲染库&#xff0c;可以通过Flutter CustomPainter原生渲染动画&#xff0c;为您带来高性能&#xff0c;低成本的动画体验123。 您可以按照以下步骤使用 SVGAPlayer-Flutter 插件&#xff1a; 1.在 pubspec.yaml 文件中添…...

鸿蒙开发软件汉化

一、打开设置 File>Settings>Plugins>Marketplace&#xff0c;输入Chinese搜索插件&#xff08;有的人是搜不到的&#xff09;&#xff0c;但别慌&#xff0c;选择Marketplace傍边的 Installed 按钮&#xff0c;里面就有Chinese插件(如果搜索出来的东西比较多往下就可…...

Three.js Tri-panner (三面贴图) 材质 两种实现方式

文章目录 介绍自定义shaderNodeMaterial骨骼材质特殊处理 介绍 Tri-panner 在babylonjs中有支持 但是three.js目前的基础材质并不支持 需要自己定义shader 或者使用目前还没有什么完善的文档的 NodeMaterial 下面展示两种实现方式 自定义shader /*** description: 替换三角面…...

Docker部署Flask项目

Docker部署Flask项目 一、准备项目代码二、编写Dockerfile三、服务器部署 一、准备项目代码 这里写了一个简单的Flask的demo&#xff0c;源代码如下&#xff1a; from flask import Flaskapp Flask(__name__)app.route("/") def index():return "<h1 styl…...

Git将某个文件合并到指定分支

企业开发中&#xff0c;经常会单独拉分支去做自己的需求开发&#xff0c;但是某些时候一些公共的配置我们需要从主线pull&#xff0c;这时候整个分支merge显然不合适 1.切换至待合并文件的分支 git checkout <branch>2.将目标分支的单个文件合并到当前分支 git checkou…...

Dockerfile构建镜像以及阿里云上传

前言 我们在使用docker部署微服务项目的时候会发现这样一个问题&#xff1a;每个服务构建出的镜像文件都很大&#xff0c;几百M&#xff0c;有些原始镜像也已经占据了很多内存了... 这种大的镜像往往都会导致迁移的速度变慢。其实我们启动容器主要最需要的镜像是jdk&#xff0…...

锂离子电池建模综述

锂电池很有吸引力&#xff0c;因为在元素周期表中&#xff0c;锂是一种非常正电的元素&#xff0c;它也恰好是最轻的金属&#xff0c;密度是水的一半。通常&#xff0c;电池由串联/并联的电化学电池组成。每个电池都包含一个负极&#xff08;放电时为阳极&#xff09;和一个由电…...

获取淘宝商品销量数据的方法分享(API、爬虫技术)

随着电子商务的飞速发展&#xff0c;获取淘宝商品销量数据的需求越来越强烈。无论是商家、分析师还是研究人员&#xff0c;都需要这些数据来了解市场趋势、竞争对手情况以及制定营销策略。本文将分享如何通过API和爬虫技术获取淘宝商品销量数据。 一、API获取数据 淘宝开放平…...

android 自定义八边形进度条

自定义八边形动画效果图如下 绘制步骤&#xff1a; 1.先绘制橙色底部八边形实心 2.黑色画笔绘制第二层&#xff0c;让最外层显示一条线条宽度即可 3.再用黄色画笔绘制黄色部分 4.使用渐变画笔根据当前进度绘制覆盖黄色部分 5.使用黑色画笔根据当前进度绘制刻度条 6.黑色画笔绘制…...

域名群站开源系统分享开源域名授权系统

一、需要自己安装PHP和MYSQL服务器环境。 二、务必设置伪静态规则&#xff0c;否则将无法访问文章栏目页面。 三、启用伪静态功能&#xff0c;请在站点设置中选择使用thinkphp的伪静态规则。 四、在域名的根目录下找到”data/config.php”文件&#xff0c;填入数据库的账号和…...

CTF - Web 干货

目录 1、php反序列化之pop链构造 2、常见php伪协议的使用 &#xff08;1&#xff09;php://filter &#xff08;2&#xff09;php://input 3、文件上传常规操作 (1) 前端绕过 (2) 修改文件类型 (3) 配合.user.ini 或.htaccess解析 (4) 爆破可解析后缀 (5) 针对Windows…...

mobi文件怎么转换成pdf?

mobi文件怎么转换成pdf&#xff1f;在数字化时代&#xff0c;电子书籍成为了越来越受欢迎的阅读方式。我们可以通过多种格式的电子书来获取知识和娱乐&#xff0c;其中一种常见的格式就是Mobi文件。Mobi文件是亚马逊公司开发的一种电子书格式&#xff0c;它主要用于Kindle设备和…...

spakr 提交任务

当前集群支持3中集群管理 Standalone&#xff08;spak框架自身拥有能力&#xff09;Apache Mesos Hadoop YARN Kubernetes 使用/spark-submit脚本提交任务&#xff0c;脚本后面可以接参数 ./bin/spark-submit \--class <main-class> \--master <master-url> \--de…...

What is `addFormattersdoes` in `WebMvcConfigurer` ?

addFormatters 方法在SpringMVC框架中主要用于向Spring容器注册自定义的格式化器&#xff08;Formatter&#xff09; SpringMVC内置了一系列的标准格式化器&#xff0c;用于处理日期、数字和其他常见类型的转换。 开发者也可以通过实现 WebMvcConfigurer 接口&#xff0c;并重写…...

新冠疫情数据可视化分析大屏

项目背景&#xff1a; 新冠疫情的爆发对全球造成了深远的影响&#xff0c;实时监控和数据分析成为公共卫生管理的重要组成部分。为了更好地追踪疫情动态&#xff0c;本项目旨在开发一个集疫情数据采集、处理、分析与可视化于一体的大屏监控系统。 项目介绍&#xff1a; 本项…...

c#异形窗体遮罩效果

c#异形窗体遮罩效果&#xff0c;移动&#xff0c;关闭&#xff0c;最大化&#xff0c;最小化&#xff0c;还原操作 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Drawing.Drawing2D…...

橘子学Mybatis07之Mybatis关于缓存的设计

很逆天的一件事是&#xff0c;我上一次发mybatis是在2022年10月15号&#xff0c;然后直到今天才开始总结下一篇Mybatis的东西。一年里面忙成那啥了&#xff0c;而且重心都投入在了Elasticsearch的学习上面&#xff0c;基本一年下来都在搞ES&#xff0c;并且考下了ECE认证&#…...

怎样制作一本旅游电子相册呢?

​随着数码技术的发展&#xff0c;旅游电子相册已成为越来越多旅游爱好者的必备工具。它不仅能让您随时随地欣赏自己的旅行回忆&#xff0c;还能分享给亲朋好友&#xff0c;甚至上传到社交媒体上&#xff0c;让更多人了解您的旅行故事。那么&#xff0c;如何制作一本精美的旅游…...

Windows搭建OpenCV环境(Python+Anaconda)

Windows搭建OpenCV环境(PythonAnacondapycharm) Anaconda&#xff0c;中文大蟒蛇&#xff0c;是一个开源的Python发行版本&#xff0c;其包含了conda、Python等180多个科学包及其依赖项。其中包含python调opencv相关的依赖&#xff0c;相当于大礼包全家桶。 下载地址&#xf…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...