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

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

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

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

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...