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

力扣上的经典问题:接雨水

力扣上的经典问题:接雨水

在众多的编程题库中,力扣(LeetCode)是一个非常受欢迎的平台,拥有大量的算法和数据结构练习题。其中,接雨水(Trapping Rain Water)问题因其巧妙的思路和广泛的应用场景,成为了经典的面试题之一。在这篇博客中,我将介绍这个问题的背景,解决思路,并给出用C语言实现的解决方案。

问题描述

接雨水问题的描述如下:

给定一个表示高度的数组,数组中的每个元素表示一个柱子的高度,柱子之间的宽度为1。求出这个柱子图形在下雨之后能够接多少雨水。

举例来说,给定高度数组:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

该数组表示的图形如下图所示:

          ##   ###   ##  ###############

通过图形可以看出,能够接住的雨水总量为6。

解题思路

解决这个问题的方法有很多种,常见的有以下几种:

  1. 暴力法:对于每一个柱子,分别计算其左右两边的最大高度,然后取其最小值减去柱子自身的高度,累加所有柱子能够接住的水量。
  2. 动态编程:预先计算每一个柱子的左边最高高度和右边最高高度,然后同样计算水量。
  3. 双指针法:使用双指针从两端向中间遍历,计算能够接住的水量。

下面我们主要介绍双指针法,这种方法时间复杂度为O(n),空间复杂度为O(1),比较高效。

C语言代码实现

#include <stdio.h>int trap(int* height, int heightSize) {if (heightSize == 0) return 0;int left = 0, right = heightSize - 1;int left_max = 0, right_max = 0;int water = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= left_max) {left_max = height[left];} else {water += left_max - height[left];}left++;} else {if (height[right] >= right_max) {right_max = height[right];} else {water += right_max - height[right];}right--;}}return water;
}int main() {int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};int size = sizeof(height) / sizeof(height[0]);int result = trap(height, size);printf("The amount of trapped rain water is: %d\n", result);return 0;
}

代码解析

  1. 初始化变量

    • leftright 分别指向数组的两端。
    • left_maxright_max 分别记录左右两边的最大高度。
    • water 用于累加接住的雨水总量。
  2. 双指针遍历

    • 当左指针指向的高度小于右指针指向的高度时,处理左指针指向的柱子:
      • 如果当前高度大于或等于 left_max,更新 left_max
      • 否则,将 left_max 减去当前高度,得到当前柱子能接住的雨水量,累加到 water
    • 当右指针指向的高度小于等于左指针指向的高度时,处理右指针指向的柱子:
      • 如果当前高度大于或等于 right_max,更新 right_max
      • 否则,将 right_max 减去当前高度,得到当前柱子能接住的雨水量,累加到 water
  3. 输出结果:最终 water 中累加的值即为总共能接住的雨水量。

总结

接雨水问题是一个经典的动态规划问题,通过不同的方法可以优化时间和空间复杂度。双指针法因其较低的时间复杂度和空间复杂度,成为了面试中常见的解法之一。希望这篇博客能够帮助大家更好地理解接雨水问题,并掌握其解决思路和方法。


希望这篇博客对你有帮助!如果你有任何问题或需要进一步的解释,请随时告诉我。

相关文章:

力扣上的经典问题:接雨水

力扣上的经典问题&#xff1a;接雨水 在众多的编程题库中&#xff0c;力扣&#xff08;LeetCode&#xff09;是一个非常受欢迎的平台&#xff0c;拥有大量的算法和数据结构练习题。其中&#xff0c;接雨水&#xff08;Trapping Rain Water&#xff09;问题因其巧妙的思路和广泛…...

双例集合(二)——双例集合的实现类之HashMap容器类

双例集合的常用实现类有HashMap和TreeMap两个&#xff0c;通过这两个类我们可以实现Map接口定义的容器&#xff0c;一般情况下使用HashMap容器类较多。 HashMap容器类是Map接口最常用的实现类&#xff0c;它的底层采用Hash算法来实现&#xff0c;这也就满足了键key不能重复的要…...

oracle-定时器(job)

--1分钟运行一次定时任务。sysdate为了定时任务即可生效。 DECLARE JOB NUMBER; BEGIN DBMS_JOB.SUBMIT(JOB,P_HJZ_HJZ_PJ_DDYTKAPB_INIT_JOB;,SYSDATE,sysdate1/24/60); COMMIT; END; / select * from user_jobs; --删除 begin DBMS_JOB.broken (462, false); DBM…...

cron.timezone

系统 date 数据库 show timezone插件 show cron.timezonealter system set cron.timezonePRC;show cron.timezone...

Hadoop+Spark大数据技术(测试)

1、九九乘法表 在下面的单元格中编写Scala程序&#xff0c;输出上三角形的九九乘法表&#xff0c;并运行。 for (i <- 1 to 9 reverse) {for (j <- 1 to i) {print(s"$j x $i ${i * j}\t")}println() } 2、单词计数 在下面的若干单元格中编写Spark程序&#…...

使用新语法连接Qt 5中重载的信号和槽

在使用Qt 5中的新信号和槽连接语法&#xff08;使用成员函数指针&#xff09;时&#xff0c;我遇到了一些问题。根据新的信号槽语法的描述&#xff0c;我尝试将以下代码&#xff1a; QObject::connect(spinBox, SIGNAL(valueChanged(int)),slider, SLOT(setValue(int)));改为&…...

梯度提升决策树(GBDT)的训练过程

以下通过案例&#xff08;根据行为习惯预测年龄&#xff09;帮助我们深入理解梯度提升决策树&#xff08;GBDT&#xff09;的训练过程 假设训练集有4个人&#xff08;A、B、C、D&#xff09;&#xff0c;他们的年龄分别是14、16、24、26。其中A、B分别是高一和高三学生&#x…...

路由器的Wi-Fi性能是否限制了你的网速?这里有你想要的答案

​你的无线网络速度阻碍了你吗?信不信由你,升级到超快的互联网计划可能不值得。以下是如何判断路由器的Wi-Fi速度是否阻碍了你,以及你能做些什么。 如何测试你的Wi-Fi速度 比较你的有线速度和无线速度可以表明你的路由器是否阻碍了你。虽然很多人认为“Wi-Fi”和“互联网”…...

简站WordPress是最简洁好用易上手的wordpress企业建站主题

简站WordPress主题确实是一个非常简洁、好用且易上手的企业建站主题。以下是详细分析&#xff1a; 简洁性&#xff1a;简站WordPress主题采用了扁平化设计风格&#xff0c;界面简洁明了&#xff0c;这使得它在众多WordPress主题中脱颖而出。这种设计不仅美观&#xff0c;还能提…...

阿里云 debian10.3 sudo apt-get updat 报错的解决方案

阿里云全新的debian10.3(buster)镜像&#xff0c;却无法正常执行 sudo apt-get update。主要报错信息如下&#xff1a; Err:6 http://mirrors.cloud.aliyuncs.com/debian buster-backports Release404 Not Found [IP: 100.100.2.148 80] Err:3 http://mirrors.cloud.aliyuncs…...

vite中使用scss技巧

一、样式混合 1.普通用法 mixin flex() {display: flex;justify-content: space-around;align-items: center; }//使用方法 .legend_box_item {width: 50%;height: 10px;include flex; }2.传递参数&#xff0c;参数后面的值为默认值 mixin flex($justify: flex-start, $alig…...

PyQt5/Pyside2学习记录

前言 最近导师的项目要求是PyQt&#xff0c;现学现用&#xff0c;现在写下中间的一些注意事项。 本程序分为两个界面&#xff0c;要求两个界面能堆叠显示&#xff0c;一个首页界面&#xff0c;一个功能界面。在功能界面中&#xff0c;有三个操控的控件&#xff0c;下拉框、文本…...

记一次通过脚本来实现自定义容器的自动重启

通过脚本来实现自定义容器的自动重启 1. 场景还原2. 自定义启动脚本3. 使用自定义脚本来作为容器启动的脚本4. 制作自定义脚本作为入口点的新镜像5. 测试新镜像启动是否走自定义启动脚本 1. 场景还原 现在我有一个自定义的Docker镜像&#xff0c;是基于基础镜像来构建的带有多…...

基于Django、Bootstrap的电影推荐系统,算法基于用户的协同过滤算法,有爬虫有可视化后台

背景 基于Django和Bootstrap的电影推荐系统结合了用户协同过滤算法&#xff0c;通过爬虫技术获取电影数据&#xff0c;并在可视化后台展示推荐结果。该系统旨在提供个性化的电影推荐服务&#xff0c;帮助用户发现符合其喜好的电影。 用户协同过滤算法是一种常用的推荐算法&am…...

mysql、mariadb 登录主机的含义,如何修改登录主机,如何删除登录主机

MariaDB版本: 10.3.39 登录主机的含义&#xff1a; 参考 1 阿风说事&#xff1a;说世间百态、聊奇闻趣事&#xff0c;分享个人观点和独到见解 2 mysql授权localhost&%区别及一直授权错误解决办法&#xff08;安装openstack有感&#xff09; 3 ERROR 1396 (HY000): Operat…...

c++ 设计模式 的课本范例

&#xff08;1&#xff09; 框架设计模式 model mode &#xff1a; 算法的框架不变&#xff0c;算法的细节可以改变。主要依赖多态。 class Player { protected:int life;int magic;int attack;virtual void effect_self() {}virtual void effect_enemy() {}virtual bool can_…...

QT中绘制点阵

1.QGraphicsScene&#xff0c;QGraphicsView&#xff0c;QGraphicsItem机制 #include <QApplication> #include <QGraphicsView> #include <QGraphicsScene> #include <QGraphicsEllipseItem>int main(int argc, char *argv[]) {QApplication app(arg…...

机器人里程计(Odometry)

机器人里程计&#xff08;Odometry&#xff09;是机器人定位和导航中的一个关键概念&#xff0c;它涉及到利用传感器数据来估计机器人在环境中的位置和姿态。里程计的基本原理是根据机器人自身动作的反馈来计算其相对于初始位置的位移。这通常包括机器人从一个已知位置开始&…...

后端实现预览pdf,mp4,图片

PDF预览 /*** pdf预览* param response*/RequestMapping(value "/preview")public void showPdf(HttpServletResponse response) {try {//String filePath this.getClass().getClassLoader().getResource("../../static/pdf/readme.pdf").getPath();Stri…...

【C++】数据类型、函数、头文件、断点调试、输入输出、条件与分支、VS项目设置

四、基本概念 这部分和C语言重复的部分就简写速过&#xff0c;因为我之前写过一个C语言的系列&#xff0c;非常详细。C和C这些都是一样的&#xff0c;所以这里不再一遍遍重复码字了。感兴趣的同学可以翻看我之前的C语言系列文章。 1、数据类型 编程的本质就是操作数据。 操…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...