力扣刷题--42.接雨水【图文详解|超级详细】

news/2024/11/29 1:43:38/

在你没有全力以赴之前,都不要抱怨环境,等你努力做到极限了再说

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出:6

解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]

输出:9

提示:

n == height.length

1 <= n <= 2 * 104

0 <= height[i] <= 105

思路分析

  • 思考每一个位置能接多少雨水,比如位置5,他的水量是2,2是怎么来的呢?

  • 答:从5号位置向左找最大高度,显然为2,向右找最大高度,显然为3,由于短板效应,水必然会从木板短的流走,故取min(left_max,right_max),然后再减去自己的高度,就是盛水量即min(2,3)-0=2

  • 抽象出来就是 i位置的当前水量=min(left_max,right_max)-height[i]

  • 注意:如果min(left_max,right_max)-height[i]这个数值小于0,那么取0,可能i位置没有水,但不会为负数,如下图所示。

  • 接下来,问题就转化为每一个位置的left_max,和right_max如何求?

  • 答:使用两个辅助数组,记录下每个位置i, left_max[i] height[0] height[i] 的最大值和 right_max[i] height[i] height[n-1] 的最大值

  • 时间复杂度O(n), 空间复杂度O(n)

  • 在此基础上可以继续优化,使用双指针,不需要辅助数组,做到空间复杂度O(1)

  • 使用有限几个变量,l,r,left_max,right_max

  • 使用双指针,配合了单调性分析,增加了左侧部分最大值,和右边部分最大值,left_maxright_max谁是小的一旦暴漏,就可以结算那一侧当前的水量。此时就优化了之前的辅助数组。

  • 举个例子

  • 由于0位置的left_max<11位置的right_max,那么左侧位置的l就可以结算答案了,为min(0,1)-1=-1,所以取水量0

  • 为什么呢?因为1位置的水量是由min(left_max,right_max)决定的,而左侧部分的最大值已经出现了,故可以结算答案

完整代码

//未优化版本
class Solution {
public:int trap(vector<int>& height) {//i位置的雨水==min(左max,右max)-height[i]//由于短板效应,水会从较为小的那一边流淌出去//注:如果减出来是负数,说明没有水// 使用辅助空间pre_max,suf_max// 0-i范围上的最大值,记录在lmax[i]int n=height.size();vector<int>pre_max(n);vector<int>suf_max(n);pre_max[0]=height[0];suf_max[n-1]=height[n-1];for(int i=1;i<n;i++){pre_max[i]=max(pre_max[i-1],height[i]);}for(int i=n-2;i>=0;i--){suf_max[i]=max(suf_max[i+1],height[i]);}int ans=0;for(int i=0;i<n;i++){int tmp=min(pre_max[i],suf_max[i])-height[i];if(tmp>0){ans+=tmp;}}return ans;}
};//优化版本
class Solution {
public:int trap(vector<int>& nums) {int l = 1;//0位置是没有水量的int r = nums.size() - 1;//最后一个位置是没有水量的,故初始化为倒二int lmax = nums[0];//第一个位置int rmax = nums[nums.size() - 1];//最后一个位置int ans=0;while (l <= r) {//谁一旦暴漏,就是小,就可以结算哪一侧的答案if (lmax <= rmax) {ans += max(0, lmax - nums[l]);//结算左侧答案lmax = max(lmax, nums[l++]);//更新左侧最大值}else{ans += max(0, rmax - nums[r]);//结算右侧答案rmax = max(rmax, nums[r--]);//更新右侧最大值}}return ans;}
};

http://www.ppmy.cn/news/1550779.html

相关文章

Git 使用问题与解决方案

Git 使用问题与解决方案 目录 常见错误及原因分析检查当前使用 HTTPS 或 SSH如何切换远程仓库到 SSHSSH 密钥的配置与验证错误解决步骤总结与参考 1. 常见错误及原因分析 错误提示 fatal: unable to access https://github.com/username/repository.git/: Failed to connect…

registry 删除私有仓库镜像

原文链接&#xff1a;https://blog.csdn.net/yogima/article/details/122172744 如果需要彻底删除&#xff0c;只需进行register 磁盘删除镜像 彻底删除了&#xff0c;就可以到达彻底删除的目的。 如果只需要软删除&#xff0c;则只需进行通过API删除。 curl --header "Ac…

python excel接口自动化测试框架!

今天采用Excel继续写一个接口自动化测试框架。 设计流程图 这张图是我的excel接口测试框架的一些设计思路。 首先读取excel文件&#xff0c;得到测试信息&#xff0c;然后通过封装的requests方法&#xff0c;用unittest进行测试。 其中&#xff0c;接口关联的参数通过正则进…

Gstreamer中,appsink、appsrc、fakesink与第三方交互

gstreamer中,有多种方式和第三方交互,其中比较推荐的有appsink、appsrc,其实还有fakesink。 appsink和appsrc即可以成对使用,也可以单独使用。appsink和fakesink用于将gst管道的数据发送出去,appsrc可以接收数据。类似opencv那种,做了封装,可以运行gst管道,可以直接运行…

【设计模式】【结构型模式(Structural Patterns)】之适配器模式(Adapter Pattern)

1. 设计模式原理说明 适配器模式&#xff08;Adapter Pattern&#xff09; 是一种结构型设计模式&#xff0c;它允许不兼容的接口协同工作。适配器模式可以将一个类的接口转换成另一个接口&#xff0c;使得原本由于接口不兼容而不能一起工作的类可以一起工作。适配器模式分为两…

Java MySQL 连接

Java MySQL 连接 本章节我们为大家介绍 Java 如何使用 使用 JDBC 连接 MySQL 数据库。 Java 连接 MySQL 需要驱动包&#xff0c;最新版下载地址为&#xff1a;http://dev.mysql.com/downloads/connector/j/&#xff0c;解压后得到 jar 库文件&#xff0c;然后在对应的项目中导…

鸿蒙面试 --- 性能优化

性能优化可以从三个方面入手 感知流畅、渲染性能、运行性能 感知流畅 在应用开发中&#xff0c;动画可以为用户界面增添生动、流畅的交互效果&#xff0c;提升用户对应用的好感度。然而&#xff0c;滥用动画也会导致应用性能下降&#xff0c;消耗过多的系统资源&#xff0c;…

信息技术与数据安全:打造高效、安全的数据处理系统

信息技术与数据安全&#xff1a;打造高效、安全的数据处理系统 在当今这个信息化高速发展的时代&#xff0c;数据已成为企业运营和决策的核心资源。随着大数据、云计算、人工智能等信息技术的飞速发展&#xff0c;数据处理能力得到了前所未有的提升&#xff0c;但同时也对数据…