首页 > 试题广场 >

接雨水问题

[编程题]接雨水问题
  • 热度指数：92095 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)


数据范围：数组长度 ，数组中每个值满足 ，保证返回结果满足
要求：时间复杂度
示例1

输入

[3,1,2,5,2,4]

输出

5

说明

数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。
示例2

输入

[4,5,1,3,2]

输出

2
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-22 13:07:02
精华题解 题目主要信息: 给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数 在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子 数组以外的区域高度视为0 举一反三： BM93. 盛水最多的容器 方法：双指针(推荐使用) 知识点：双指针 双指针指的是在遍历对象的 展开全文
去ta的博客 赞 (57) 回复(4) 收起
头像 游骑兵PXZ
发表于 2020-11-19 22:10:49
public static long maxWater(int[] arr) { if (arr == null || arr.length <= 2) { return 0; } int left = 0, right 展开全文
去ta的博客 赞 (56) 回复(5) 收起
头像 数据结构和算法
发表于 2021-04-03 22:21:21
1，三指针求解 这题让求柱子中间能盛多少水，首先可以肯定两边的两个柱子是不能盛水的，只有两边之间的柱子有可能会盛水。最简单的一种方式就是使用3个指针，先找到最高的柱子，用一个指针top指向最高柱子，然后最高柱子左边用两个指针，一个left，一个right（这里的left和right指向柱子的高度）。 展开全文
去ta的博客 赞 (44) 回复(5) 收起
头像 ❀花
发表于 2020-12-12 19:06:26
遍历两遍，从左往右遍历保存当前最大值，从右往左遍历保存当前最大值，然后容水量为 两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。 class Solution { public: /** * max water * @param arr int整型vector 展开全文
去ta的博客 赞 (17) 回复(5) 收起
头像 ButterFlyEffect
发表于 2020-10-20 23:25:09
暴力求解法 开始时想到了暴力求解法，最差情况下是O(nn)的时间复杂度，很不幸，超时了。但至少在面试的时候，可以在有限的时间内给出一个基本解法，思路是这样的：1 在数组arr(left, right)中找出最大和第二大的数的位置pos1和pos2；这样就将arr划分成了3段： left,..., 展开全文
去ta的博客 赞 (16) 回复(1) 收起
头像 飘过的小牛
发表于 2021-03-15 11:37:27
本题的题目描述不太明确，需要一张示意图，在看别人的题解时看到这个图才明白是怎么回事。 所以本题的核心就是构造两边高而中间低的桶，这个桶能装的水取决于两边里面比较短的那一边。比如{3，1，2} 这个数组能装的水等于1 求得两边的最小值 22 用短的边减去中间波谷的值1得到结果1则数组{3，1，2} 这 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 淡然处之_
发表于 2021-03-09 19:46:57
很多人是没有理解题目，下面是别人的代码问题的关键是找到最小边界。如图 import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 王清楚
发表于 2021-03-29 14:41:40
题目可以转化为求每个位置上面能装多少水比如题目中给出来的例子：左右两边边界(0和5位置)上是一定不会有水的，然后1位置上能装2格水，2位置上能装1格水，3位置上不能装水，4位置上能装2格水。所以对于这一个例子来说，一共能装5格水。那么我们就再来考虑一下，每个位置上面能装多少水怎么求对于位置 来说， 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 宫水三叶的刷题日记
发表于 2021-08-26 15:59:35
朴素解法 对于每根柱子而言，我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。 对左右的最高柱子取一个最小值，再和当前柱子的高度做一个比较，即可得出当前位置可以接下的雨水。 同时，边缘的柱子不可能接到雨水（某一侧没有柱子）。 这样的做法属于「暴力做法」，但题目没有给数据范围，我们无法分析到底 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 LaN666
发表于 2020-11-25 20:27:51
思路分析：因为要该容器是一个高低不平的容器，所以我们直接找出容器的左右边界，很明显，为了不让水溢出来，容器的边界肯定取那个更低的。然后使用双指针，分别从两边往中间扫描，如果此时左边arr[left]的高度小于右边的高度时，左指针向右扫描+1，如果此时当前位置的高度小于容器的边界高度，那么意味着此位置 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 小时光s3o
发表于 2021-08-05 05:04:00
题解 | #接雨水问题#C++ 解法，双指针，理解短边移动 class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ 展开全文
去ta的博客 赞 (5) 回复(1) 收起

问题信息

动态规划 单调栈 双指针
难度：
215条回答 8729浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号