从暴力到动态规划再到双指针：使用 Java 探索接雨水问题的不同解法
文章目录
- 一、问题描述
- 二、暴力法（Brute Force）
- 思路
- 实现代码
- 三、动态规划法（Dynamic Programming）
- 思路
- 实现代码
- 四、双指针法（Two Pointers）
- 思路
- 实现代码
- 五、方法对比
在本文中，我们将探讨经典的接雨水问题，并提供多种解题思路和方法。通过逐步深入的方式，将了解到如何使用暴力法、动态规划法以及双指针法解决这一问题，并对它们进行性能对比。
一、问题描述
42.接雨水
二、暴力法（Brute Force）
思路
对于数组中的每一个元素，我们都可以找到它左边和右边的最大高度，然后根据这两个最大高度来确定当前元素能够接住的水量。
实现代码
public int trap(int[] height) {int totalWater = 0;for (int i = 1; i < height.length - 1; i++) {int maxLeft = 0, maxRight = 0;// 寻找左边最高的柱子for (int j = i; j >= 0; j--) {maxLeft = Math.max(maxLeft, height[j]);}// 寻找右边最高的柱子for (int j = i; j < height.length; j++) {maxRight = Math.max(maxRight, height[j]);}// 计算当前位置可以存储的水totalWater += Math.min(maxLeft, maxRight) - height[i];}return totalWater;
}
时间复杂度：O(n^2)，因为对于每个元素都需要遍历其左右两边来寻找最大值。
空间复杂度：O(1)。
三、动态规划法（Dynamic Programming）
思路
为了避免重复计算每个位置的左右最大高度，我们可以预先计算并存储这些信息。这样，当我们计算某个位置能接多少水时，可以直接查表得到左右最大高度。
实现代码
public int trap(int[] height) {if (height == null || height.length == 0) return 0;int n = height.length;int[] leftMax = new int[n], rightMax = new int[n];// 初始化最左边和最右边的边界条件leftMax[0] = height[0];rightMax[n - 1] = height[n - 1];// 填充leftMax数组for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}// 填充rightMax数组for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}// 计算总储水量int totalWater = 0;for (int i = 0; i < n; i++) {totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];}return totalWater;
}
时间复杂度：O(n)，因为我们只需要遍历数组三次。
空间复杂度：O(n)，需要额外的空间来存储左右最大高度。
四、双指针法（Two Pointers）
思路
利用两个指针分别从数组的两端向中间移动，并同时维护左右两侧的最大高度。这种方法可以在一次遍历中解决问题，无需额外的空间。
实现代码
public int trap(int[] height) {if (height == null || height.length == 0) return 0;int left = 0, right = height.length - 1;int maxLeft = 0, maxRight = 0;int totalWater = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= maxLeft) {maxLeft = height[left];} else {totalWater += maxLeft - height[left];}left++;} else {if (height[right] >= maxRight) {maxRight = height[right];} else {totalWater += maxRight - height[right];}right--;}}return totalWater;
}
时间复杂度：O(n)，只需遍历一次数组。
空间复杂度：O(1)，只使用了常数级别的额外空间。
五、方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力法 | O(n^2) | O(1) | 易于理解和实现 | 效率低下，不适用于大数据集 |
| 动态规划法 | O(n) | O(n) | 高效处理中等规模数据 | 需要额外的存储空间 |
| 双指针法 | O(n) | O(1) | 最优的时间和空间复杂度 | 理解难度较高 |
通过上述三种方法的介绍和比较，我们可以看到双指针法以其优秀的时空复杂度成为解决该问题的最佳选择。然而，理解不同的方法有助于我们在面对类似问题时能够灵活运用算法思维，选择最适合当前场景的解决方案。
相关文章：
从暴力到动态规划再到双指针：使用 Java 探索接雨水问题的不同解法
文章目录 一、问题描述二、暴力法（Brute Force）思路实现代码 三、动态规划法（Dynamic Programming）思路实现代码 四、双指针法（Two Pointers）思路实现代码 五、方法对比 在本文中，我们将探讨经典…...
 Jenkins共享库与k8s集成)
CI/CD(十) Jenkins共享库与k8s集成
一、创建k8skey（v1.28.2版本） 1、查看k8s集群名称 rootk8s-master:~# kubectl config get-contexts CURRENT NAME CLUSTER AUTHINFO NAMESPACE * kubernetes-adminkubernetes kubernetes kuber…...
5.Elasticsearch - Spring Data 框架
一、Kibana 介绍 Kibana 是一个免费且开放的用户界面，能够让你对 Elasticsearch 数据进行可视化，并让你在 Elastic Stack 中进行导航。你可以进行各种操作，从跟踪查询负载，到理解请求如何流经你的整个应用，都能轻松完…...
如何通过技术手段降低开发成本
通过技术手段降低开发成本的关键在于： 自动化工具的使用、优化开发流程、云计算资源的利用、开发技术栈的精简与创新、团队协作平台的高效管理。 其中，自动化工具的使用是最为有效的技术手段之一。自动化工具通过减少人工干预和重复性工作，大…...
java android持久化数据
1. SQLite 数据库（Android 内置） 1.1 创建数据库帮助类 public class DatabaseHelper extends SQLiteOpenHelper {private static final String DATABASE_NAME "MyDatabase.db";private static final int DATABASE_VERSION 1;// 表名和列名…...
Chromium 134 编译指南 macOS篇：系统环境准备（一）
1. 引言 在当今浏览器领域，开源项目Chromium的地位举足轻重。作为众多现代浏览器的技术基础，Chromium不仅驱动着Google Chrome，还为Microsoft Edge、Opera等众多知名浏览器提供了核心引擎。对于热衷于浏览器技术研究，或希望开发自…...
性能优化-Spring参数配置、数据库连接参数配置、JVM调优
SpringBoot配置参数 server:tomcat:#线程池配置max-threads: 200 # 最大工作线程数（建议：2~4倍CPU核心数，如16核设200-400）min-spare-threads: 20 # 最小空闲线程（应对突发流量，…...
【2025年泰迪杯数据挖掘挑战赛】B题 数据预处理+问题建模与求解
目录 2025年泰迪杯数据挖掘挑战赛 B题数据预处理 问题一、二建模与求解三、数据预处理3.1 基于多核并行的协同处理方法的数据读取3.2 基于多核并行协同处理的数据聚合 四、问题一五、问题一技术文档与matlab代码 2025年泰迪杯数据挖掘挑战赛 B题 数据预处理 问题一、二建模与求…...
git怎么使远程分支回退到指定的节点处
git使远程分支回退到指定的节点 引言场景描述步骤 引言 最近提交代码的时候，总将分支合并错，原本要合到A分支，结果合并到了B分支，这样就导致b分支需要回退到我没有合并之前的节点处。 本文记录下怎么将远程分支回退到指定的节点。…...
Spring Boot 使用 QQ 企业邮箱发送邮件的完整指南（含 535 错误排查）
在 Spring Boot 项目中集成邮件功能非常常见，尤其是用户注册通知、异常报警、定期报告等场景。但如果你使用的是 QQ 企业邮箱（smtp.exmail.qq.com），可能会遇到如下典型错误： 535 Error: authentication failed, system busy这篇博客将详细解析出现该问题的原因、排查路径…...
MySQL联合查询||多表查询
mysql中如何注释...
java 递归遍历JSON字符串获取某个字段的值
在 Java 中，若要递归遍历 JSON 字符串并获取特定字段的值，可借助 Jackson 库。以下是一个示例代码，它能实现递归遍历 JSON 字符串并获取指定字段的值。 import com.fasterxml.jackson.databind.JsonNode; import com.fasterxml.jackson.data…...
OceanBase4.0社区版 单机快速部署
以下内容结合OceanBase官方文档进行安装部署测试 官方文档地址：https://www.oceanbase.com/docs/common-oceanbase-database-cn-1000000002012693 一.部署方式 OceanBase 企业版： • 使用 OCP 部署 OceanBase 集群 • 使用 OBD 部署 OceanBase 集群 •…...
CExercise_05_1伪随机数_2编写程序模拟掷骰子的游戏（每一次投掷，都投掷两个骰子）
题目： 编写程序模拟掷骰子的游戏（每一次投掷，都投掷两个骰子）。每局游戏的规则如下： 第一次掷的时候： 如果点数之和为 7 或 11 则获胜； 如果点数之和为2、3或12则落败； 其他情况下的…...
【更新至2023年】2000-2023年中国气候政策不确定性指数（全国、省、市三个层面）
【更新至2023年】2000-2023年中国气候政策不确定性指数（全国、省、市三个层面） 1.时间：2000-2023年 2.来源：使用人工审计和深度学习算法MacBERT模型，基于中国《人民日报》《光明日报》《经济日报》《环球时报》《科技…...
机器学习中 提到的张量是什么？
在机器学习中， 张量（Tensor） 是一个核心数学概念，用于表示和操作多维数据。以下是关于张量的详细解析： 一、数学定义与本质 张量在数学和物理学中的定义具有多重视角： 多维数组视角 传统数学和物理学中，张量被定义为多维数组，其分量在坐标变换时遵循协变或逆变规则。例…...
【Python爬虫】简单案例介绍3
本文继续接着我的上一篇博客【Python爬虫】简单案例介绍2-CSDN博客 目录 3.3 代码开发 3.3 代码开发 编写代码的步骤： request请求科普中国网站地址url，解析得到类名为"list-block"的div标签。 for循环遍历这个div列表里的每个div࿰…...
对于客户端数据存储方案——SQLite的思考
SQLite 比较适合进行本地小型数据的存储，在功能丰富性和并发能力上不如 MySQL。 数据类型差异 SQLite 使用动态类型系统：只有 5 种基本存储类 (NULL, INTEGER, REAL, TEXT, BLOB) 类型亲和性：SQLite 会将声明的列类型映射到最接近的存储类 …...
基于Nacos+动态线程池的分布式系统弹性设计：投行交易与风控场景实战
业务痛点和需求分析 在投行高频交易系统和对公贷款风控计算引擎中，我们面临两大核心挑战： 流量洪峰波动剧烈 交易时段TPS可达10万/秒，非交易时段下降80%风控模型计算存在突发性批量任务（如月末集中评审） 架构设计与…...
高并发内存池（定长内存池基础）
定长内存池的设计 定长内存池定长内存池的原理讲解代码实现定义对象New对象的主要逻辑delete对象的主要逻辑完整代码 定长内存池 为什么我们要设计这个定长内存池呢？首先malloc是c标准库中向堆申请空间的接口，变相的说malloc是普遍性，而我们…...
element-ui plus 中 filter-method 函数多次触发问题解决
前情提要 点进这个文章的小伙伴，应该都是为了解决一个需求，把原本的前端过滤改为后端过滤，但是将filter-method修改为后端取数据后，发现其触发了很多次。博主也是在修改表格过滤时用到了这个坑，本篇文章为大家解决一下…...
物联网场景实战：智能电表数据管理与分析（一）
智能电表与物联网的融合 在当今数字化时代，随着物联网（IoT）技术的飞速发展，各行业都在积极探索如何利用这一技术实现转型升级 。电力行业也不例外，智能电表作为电力系统与物联网融合的关键节点，正发挥着越来…...
网络中的基本概念
这篇文章主要介绍我们在学习网络的过程中，会碰到的一系名词，对其概念进行解释，让大家知道这些都是干什么的。 网络：若干个节点和连接这些节点的链路组成的，用于实现信息交换资源共享。 节点：网络中各种接地…...
行锁（Row Locking）和MVCC（多版本并发控制）
在数据库系统中，**行锁（Row Locking）和MVCC（多版本并发控制）**是两种不同的并发控制机制，它们的使用场景和原理有显著区别。以下是详细对比和适用场景分析： 一、行锁（Row Locking&am…...
AlexNet神经网络详解及VGGNet模型和
AlexNet模型细节 一共8层，5个卷积层，3个全连接层 AlexNet工程技巧 多GPU训练，ReLU激活函数，LRN归一化，Dropout，重叠池化，数据增强等 多GPU训练 除了将模型的神经元进行了并行，还使…...
【Linux网络】Socket 编程TCP
🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343 🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12891150.html 目录 TCP socket API 详解 socket(): bind(): listen(): accept(): connect V0…...
代码训练day27贪心算法p1
贪心的本质是选择每一阶段的局部最优，从而达到全局最优 贪心算法一般分为如下四步： 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 1.分发饼干 先将饼干数组和小孩数组排序。 然后从后向前遍历…...
基于RV1126开发板的车辆检测算法开发
1. 车辆检测简介 车辆检测是一种基于深度学习的对人进行检测定位的目标检测，能广泛的用于园区管理、交通分析等多种场景，是违停识别、堵车识别、车流统计等多种算法的基石算法。 人脸检测算法mAP0.5CAR0.78029 基于EASY-EAI-Nano硬件主板的运行效率&…...
Leetcode——137 260找出只出现一次的数
文章目录 找出只出现一次的数引入Leetcode 260Leetcode 137 找出只出现一次的数 对于数组中有一类题，即某些数据在数组中只出现一遍，需要我们找出，今天我们来看看这个类型的题。 引入 想必大家应该见过这么一道题： 现给定一个数…...
【多线程-第四天-自己模拟SDWebImage的下载图片功能-看SDWebImage的Demo Objective-C语言】
一、我们打开之前我们写的异步下载网络图片的项目，把刚刚我们写好的分类拖进来 1.我们这个分类包含哪些文件： 1）HMDownloaderOperation类， 2）HMDownloaderOperationManager类， 3）NSString+Sandbox分类， 4）UIImageView+WebCache分类， 这四个文件吧，把它们拖过来…...
【5G学习】基本概念之多频资源以及子载波和信道
在5G通信中，子载波、信道以及时域、频域、码域、空域是构建无线传输系统的核心概念。它们共同定义了信号的传输方式、资源分配和多维复用技术。以下是详细解释及其相互关系： 一、核心概念定义 1. 子载波（Subcarrier） 定义&#…...
鸿蒙动画与交互设计：ArkUI 3D变换与手势事件详解
大家好，我是 V 哥。 在鸿蒙 NEXT 开发中，ArkUI 提供了丰富的 3D 变换和手势事件功能，可用于创建生动且交互性强的用户界面。下面详细介绍 ArkUI 的 3D 变换和手势事件，并给出相应的 ArkTS 案例代码。 1. ArkUI 3D 变换 ArkUI 支…...
敏感数据触发后怎么保障安全?
当敏感数据被触发或泄露时，需立即采取系统化措施控制风险。以下为分阶段应对策略，结合技术与管理手段： 一、即时响应阶段 阻断扩散 隔离受影响系统：立即断开网络连接、暂停服务或关闭相关端口。 终止可疑进程：通过华…...
【CVE-2024-10929】ARM CPU漏洞安全通告
安全之安全(security)博客目录导读 目录 一、概述 二、CVE详情 三、受影响产品 四、建议措施 五、致谢 六、版本历史 一、概述 在部分基于Arm架构的CPU中发现了一个潜在安全问题，称为Spectre-BSE（Branch Status Eviction，分支状态驱逐…...
高级java每日一道面试题-2025年4月06日-微服务篇[Nacos篇]-如何诊断和解决Nacos中的常见问题？
如果有遗漏,评论区告诉我进行补充 面试官: 如何诊断和解决Nacos中的常见问题？ 我回答: 在Java高级面试中诊断和解决Nacos常见问题的综合回答 在Java高级面试中，当被问及如何诊断和解决Nacos中的常见问题时，可以从以下几个方面进行详细阐述…...
【模块化拆解与多视角信息3】教育背景：学历通胀时代的生存法则
教育背景：学历通胀时代的生存法则 写在最前 作为一个中古程序猿，我有很多自己想做的事情，比如埋头苦干手搓一个低代码数据库设计平台（目前只针对写java的朋友），比如很喜欢帮身边的朋友看看简历，讲讲面试技巧，毕竟工作这么多年，也做到过高管，有很多面人经历，意见还算…...
无人机3S与4S电池技术对比！
一、基础参数对比 1. 电芯与电压 3S电池：由3节锂电芯串联组成，标称电压为11.1V（单节3.7V3），满电电压约12.6V。 4S电池：由4节电芯串联，标称电压14.8V（3.7V4）&#…...
，内核的CPUFreq(DVFS)和ARM的SCPI)
linux电源管理(二)，内核的CPUFreq(DVFS)和ARM的SCPI
更多linux系统电源管理相关的内容请看：https://blog.csdn.net/u010936265/article/details/146436725?spm1011.2415.3001.5331 1 简介 CPUFreq子系统位于drivers/cpufreq目录下，负责进行运行过程中CPU频率和电压的动态调整，即DVFS (Dynami…...
短波红外高光谱相机：高光谱成像在塑料分选中的应用
随着塑料工业的迅猛发展，塑料包装制品需求量增长迅速，消耗量不断上升，废塑料产生量也急剧增加。由于塑料化学结构稳定，难以自然降解，不当使用和处置及累积会造成严重的环境污染和资源浪费。因此，快速、精准…...
通过OBD部署OceanBase社区版集群v4.3.5
以下内容结合OceanBase官方文档进行安装部署测试 官方文档地址：https://www.oceanbase.com/docs/common-oceanbase-database-cn-1000000002016072 一.环境准备 准备三台虚拟机，配置信息如下 192.168.232.8 centos7.9 4c16g 硬盘100g 192.168.232.9 …...
【Java学习笔记】注释
注释 为什么要写注释？ 养成良好的编程习惯，方便后续阅读和查看，理顺思路，增加可读性 对自己的代码负责，对别人负责 说明 1. 被注释的文字，不会被 JVM（虚拟机）解释执行 2. 多行注…...
Python 调用 YOLO ONNX
Python 调用 YOLO ONNX 1 下载ONNX文件2 Python代码 1 下载ONNX文件 ONNX下载地址 2 Python代码 import cv2 from ultralytics import YOLO# 加载 YOLOv11 model YOLO(./yolo11n.pt)# 读取图片 image_path ./11.png img cv2.imread(image_path)# 推理（可以传…...
Linux 下 Module 工具的介绍与使用
参考： https://www.fasteda.cn/post/22.html https://modules.readthedocs.io/en/latest/module.html Linux 下 Module 工具的介绍与使用 一、前言 在 Linux 中，当同一款编辑器、运行库、软件存在多个版本且多个版本都需要在不同的场景或人员使用时&a…...
批量归一化（Batch Normalization）原理与PyTorch实现
批量归一化（Batch Normalization）是加速深度神经网络训练的常用技术。本文通过Fashion-MNIST数据集，演示如何从零实现批量归一化，并对比PyTorch内置API的简洁实现方式。 1. 从零实现批量归一化 1.1 批量归一化函数实现 import t…...
Flutter 文本组件深度剖析：从基础到高级应用
引言 在 Flutter 应用开发中，文本是向用户传达信息的重要媒介。Flutter 提供了丰富且强大的文本组件和相关属性，使开发者能够轻松实现多样化的文本展示效果。无论是简单的静态文本显示，还是复杂的富文本渲染，Flutter 都能满足需求…...
FABC是什么？
在销售和品牌营销领域，FABC 是一种用于构建销售话术和营销信息的框架，其全称为 Features（特点）、Advantages（优势）、Benefits（利益）、Case（案例）。该模型帮助…...
【MySQL】MVCC工作原理、事务隔离机制、undo log回滚日志、间隙锁
一、什么是MVCC？ MVCC，即 Multiversion Concurrency Control（多版本并发控制），它是数据库实现并发控制的一种方式。 MVCC 的核心思想是： 为每个事务提供数据的“快照”版本，从而避免加锁&…...
Spring Boot 集成 RocketMQ 全流程指南：从依赖引入到消息收发
前言 在分布式系统中，消息中间件是解耦服务、实现异步通信的核心组件。RocketMQ 作为阿里巴巴开源的高性能分布式消息中间件，凭借其高吞吐、低延迟、高可靠等特性，成为企业级应用的首选。而 Spring Boot 通过其“约定优于配置”的设计理念&a…...
PCL 点云RANSAC提取平面（非内置函数）
文章目录 一、算法实现1.1实现步骤二、实现代码三、实现效果参考资料一、算法实现 1.1实现步骤 1、确定模型。三个点确定一个平面，方程式为 a x + b y + c z + 1 = 0 ax+by+cz+1=0...
中介者模式：理论、实践与 Spring 源码解析
摘要 本论文以中介者模式为核心，系统阐述其设计原理、应用场景及在 Spring 框架中的实现机制。通过机票预订系统、银行交易系统等典型案例，具象化展示模式如何解耦复杂对象交互；结合 Spring 5.3.29 源码，深入剖析事件驱动模型中ApplicationEventPublisher与ApplicationLis…...