【力扣】42. 接雨水
这道题我卡了差不多1个小时,不是不会做,是不知道怎么能用栈来实现,后面看了一个博主的视频,豁然开朗,我主要的纠结点在于当指针指到7的时候,我计算出4到7的水块是2,但实际上是0,因为用栈是横向求解的,就是你横着来切一刀就行,然后掌握其原理。
先放代码吧,看不懂再看我的题解
class Solution {public int trap(int[] height) {//定义水块和int sum=0;Stack<Integer> stack=new Stack<>();int current=0;while(current<height.length){while(!stack.empty()&&height[current]>height[stack.peek()]){//获得栈顶元素的高度int h=height[stack.peek()]; stack.pop(); //出栈if(stack.empty()){break;}//计算方式int dt=current-stack.peek()-1;int min=Math.min(height[current],height[stack.peek()]);sum=sum+(min-h)*dt;} //存放的是坐标 stack.push(current);current+=1;}return sum;}
}
题解如下:

1.首先讲一下原理,栈,用的时候注意里面存放的是单调递增的元素,从下往上看
2.过程:
根据本题来看,首先第一个height[0]入栈,指针后移,此时指针所指向的元素大于栈顶元素,所以栈顶元素出栈。height[1]入栈,指针后移,此时指针所指向的元素小于栈顶元素,height[2]入栈指针后移,height[3]>height[2],所以height[2]出栈 ,找到height[2]左边的比他大的元素,也就是栈顶元素。这个其实是已经排序好的,懂吧,然后比较左边和右边的元素,找出最小值,再减去之前出栈的元素的高度,再乘以左右两边元素之差-1,就是这样子,这个计算方法就是这样的,后面也就以此类推了。再见!祝各位刷题人happy !
相关文章:
【力扣】42. 接雨水
这道题我卡了差不多1个小时,不是不会做,是不知道怎么能用栈来实现,后面看了一个博主的视频,豁然开朗,我主要的纠结点在于当指针指到7的时候,我计算出4到7的水块是2,但实际上是0,因为…...
IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案
一 背景 汽车ADAS技术是当下国内外的重点研究方向,且ADAS的发展水平和市场竞争力紧密相关,因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而,国内ADAS测试却面临着很多阻碍,主要原因在于:相关测试设备昂贵&am…...
Go语言中的指针介绍
Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址(Pointer Address)1.4.2 指针类型(Pointer Type)1.4.3 指针取值(Poi…...
简单理解区块链
这篇是挖矿篇详细介绍区块链之挖矿-CSDN博客的后置文章,咱们通过之前的解释进一步复习学习区块链叭! 百度百科定义 区块链,就是一个又一个区块组成的链条。每一个区块中保存了一定的信息,它们按照各自产生的时间顺序连接成链条。这…...
[尚硅谷React笔记]——第3章 React应用(基于React脚手架)
目录: react脚手架创建项目并启动react脚手架项目结构一个简单的Hello组件样式的模块化功能界面的组件化编码流程(通用)组件的组合使用-TodoList 1.react脚手架 xxx脚手架: 用来帮助程序员快速创建一个基于xxx库的模板项目 包含了所有需…...
《Linux 内核设计与实现》13. 虚拟文件系统
通用文件接口 VFS 使得可以直接使用 open()、read()、write() 这样的系统调用而无需考虑具体文件系统和实际物理介质。 好处:新的文件系统和新类型的存储介质需要挂载时,程序无需重写,甚至无需重新编译。 VFS 将各种不同的文件系统抽象后采…...
2021-06-09 51单片机:两个独立按键控制一个led,k1按下松开led闪烁三次,k2按下LED闪烁五次
缘由51单片机:两个独立按键控制一个led,k1按下松开led闪烁三次,k2按下LED闪烁五次_嵌入式-CSDN问答 #include "REG52.h" sbit K1 P1^0; sbit K2 P1^1; sbit LEDP0^0; void main() {unsigned char Xd0,ss0;unsigned int wei0;while(1){if(K10&&Xd0){ss3*2;…...
C/C++ 经典面试算法题
1.打印杨辉三角 1 #include <stdio.h>2 #include <string.h>3 4 int main()5 {6 int x;7 int a[100][100];8 printf("输入行数\n");9 scanf("%d",&x); 10 for(int i 0;i<x;i) 11 { 12 for(int j 0;…...
2023年下学期《C语言》作业0x02-分支 XTU OJ 1068 1069 1070 1071 1072
第一题 #include<stdio.h>int main() {int a;scanf("%d",&a);if(a>90&&a<100) printf("A");else printf("B");return 0; } 没有换行,不然会格式错误 第二题 #include<stdio.h>int main() {int a;s…...
JMeter学习第一、二、三天
首先,我们来了解一下到底什么是接口测试与性能测试: 接口测试 定义 接口测试主要关注系统组件之间的交互,确保各个接口按预期工作。这包括验证传递的数据、数据格式、调用的频率和其他与接口调用相关的任何限制。 目的 确保系统的各个组件可…...
常用的分布式ID解决方案原理解析
目录 前言 一:分布式ID的使用场景 二:分布式ID设计的技术指标 三:常见的分布式ID生成策略 3.1 UUID 3.2 数据库生成 3.3 数据库的多主模式 3.4 号段模式 3.5 雪花算法 前言 分布式ID的生成是分布式系统中非常核心的基础性模块&#…...
echarts3D地图打点
1、echarts地图打点加鼠标移上去显示文字 2、1-3和前面的一样echart3D地图 if (res.code 0) {const resData res.data || [];if (resData.length > 0) {for (var i 0; i < resData.length; i) {let arr new Array(2);arr[0] resData[i].longitude || ""…...
分布式主键算法
目录 一、引言二、常见算法介绍雪花算法(Snowflake Algorithm)特性详解优势劣势 UUID(Universally Unique Identifier)特性详解优势劣势 数据库自增主键特性详解优势劣势 分布式数据库的序列(Sequence)特性…...
暴力破解及验证码安全
1.暴力破解注意事项 1、破解前一定要有一个有郊的字典(Top100 TOP2000 csdn QQ 163等密码) https://www.bugku.com/mima/ 密码生成器 2、判断用户是否设置了复杂的密码 在注册页面注册一个,用简单密码看是否可以注册成功 3、网站是…...
程序无法启动,提示“找不到msvcp140.dll”或“msvcp140.dll缺失报错”解决方法
大家好!今天我来给大家分享一下msvcp140.dll丢失的解决方法。我们都知道,在运行一些软件或游戏时,经常会遇到“找不到msvcp140.dll”的错误提示,这会让我们非常苦恼。那么,这个问题该怎么解决呢?下面我将为…...
【Python查找算法】二分查找、线性查找、哈希查找
目录 1 二分查找算法 2 线性查找算法 3 哈希查找算法 1 二分查找算法 二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素…...
【MySQL实战45讲-基础篇】
基础篇 基础架构 MySQL的基本架构示意图:MySQL可以分为Server层和存储引擎层两部分。 Server层包括连接器、查询缓存、分析器、优化器、执行器等,涵盖MySQL的大多数核心服务功能,以及所有的内置函数(如日期、时间、数学和加密函…...
asp.net core中间件预防防止xss攻击
using System; using System.Text.Json; using System.Text.Json.Serialization;namespace CommonUtils {/// <summary>/// newtonsoft的转化器/// 防止xss攻击/// </summary>public class AntiXssNewtonsoftConverter : Newtonsoft.Json.JsonConverter<string&…...
jvm概述
1、JVM体系结构 2、JVM运行时数据区 3、JVM内存模型 JVM运行时内存 共享内存区 线程内存区 3.1、共享内存区 共享内存区 持久带(方法区 其他) 堆(Old Space Young Space(den S0 S1)) 持久代: JVM用持久带(Permanent Space)实现方法…...
C++简单上手helloworld 以及 vscode找不到文件的可能性原因
helloworld #include <iostream>int main() {std::cout << "hello world!" << std::endl;return 0; }输入输出小功能 #include <iostream> using namespace std; /* *主函数 *输出一条语句 */int main() {// 输出一条语句cout << &q…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
