首页 > 试题广场 >

接雨水问题

[编程题]接雨水问题
  • 热度指数：95581 时间限制：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
算法知识视频讲解
添加回答
Python3
新生力量头像 新生力量 
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        lm=rm=0
        l,r=0,len(arr)-1
        ans=0
        while l<r:
            lm=max(lm,arr[l])
            rm=max(rm,arr[r])
            if lm<rm:
                ans+=lm-arr[l]
                l+=1
            else:
                ans+=rm-arr[r]
                r-=1
        return ans

发表于 2025-09-14 09:52:33 回复(0)
Python3
末日生存指南头像 末日生存指南
class Solution:
    def maxWater(self, arr: List[int]) -> int:
        ascend_l = []
        max_seen, res = 0, 0
        # get the ascending arr from left to right
        for val in arr:
            max_seen = max(max_seen, val)
            ascend_l.append(max_seen)

        max_seen = 0
        # get the ascending arr from right to left
        for val in reversed(arr):
            max_seen = max(max_seen, val)
            res += min(max_seen, ascend_l.pop()) - val
        return res


发表于 2024-02-14 15:25:18 回复(0)
Python3
pzq头像 pzq 
# 递归（原始方法的形参，不够递归使用，再创一个）
class Solution:
    ## 写法一（用类属性记录结果，比方法同级，不会释放）
    res = 0
    def find(self, arr, ind1, ind2):
        # 终止条件
        if ind1 == ind2:
            return
        # 本次计算
        if arr[ind1] <= arr[ind2]:
            init_val = arr[ind1]
            while True:
                ind1 += 1
                if arr[ind1] < init_val:
                    self.res += init_val - arr[ind1]
                else:
                    break
        else:
            init_val = arr[ind2]
            while True:
                ind2 -= 1
                if arr[ind2] < init_val:
                    self.res += init_val - arr[ind2]
                else:
                    break
        # 继续计算相同的子问题
        self.find(arr, ind1, ind2)
 
    def maxWater(self , arr: List[int]) -> int:
        self.find(arr, 0, len(arr) - 1)
        return self.res
    
    ## 写法二（传入一个变量记录结果，依次累计，最终结果一层层return）
    def find(self, arr, ind1, ind2, res=0) -> int:
        """
        ind1: int, 左边的游标
        ind2: int, 右边的游标
        res: int, 用于记录之前已接的雨水数量
        思路: res记录之前的雨水, 然后加上本轮的雨水, 最终一层层最终返回结果
        """
        # 终止条件
        if ind1 == ind2:
            return res  # 最后一轮雨水量为零, 返回最终结果
        # 本次计算
        if arr[ind1] <= arr[ind2]:
            init_val = arr[ind1]
            while True:
                ind1 += 1
                if arr[ind1] < init_val:
                    res += init_val - arr[ind1] # 加上本坑的雨水数量
                else:
                    break
        else:
            init_val = arr[ind2]
            while True:
                ind2 -= 1
                if arr[ind2] < init_val:
                    res += init_val - arr[ind2]
                else:
                    break
        # 继续计算相同的子问题
        return self.find(arr, ind1, ind2, res)
 
    def maxWater(self , arr: List[int]) -> int:
        return self.find(arr, 0, len(arr) - 1)

    ## 写法三（每次只关心当前轮结果，一层层累加，最后一轮return标志层结束，并return所有层的最终结果）
    def find(self, arr, ind1, ind2) -> int:
        """
        ind1: int, 左边的游标
        ind2: int, 右边的游标
        """
        # 终止条件
        if ind1 == ind2:
            return 0  # 结束池塘雨水量为零
        # 本次计算
        res = 0 # 记录本池塘的雨水量
        if arr[ind1] <= arr[ind2]:
            init_val = arr[ind1]
            while True:
                ind1 += 1
                if arr[ind1] < init_val:
                    res += init_val - arr[ind1] # 加上本坑的雨水数量
                else:
                    break
        else:
            init_val = arr[ind2]
            while True:
                ind2 -= 1
                if arr[ind2] < init_val:
                    res += init_val - arr[ind2]
                else:
                    break
        # 继续计算相同的子问题
        res += self.find(arr, ind1, ind2)   # 加上之后池塘的雨水量
        return res  # 返回所有池塘的累加结果

    def maxWater(self , arr: List[int]) -> int:
        return self.find(arr, 0, len(arr) - 1)

发表于 2023-05-20 16:07:44 回复(0)
Python3
JianYue头像 JianYue 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        ret = 0
        stack = []
        for i in range(len(arr)):
            if stack:
                if arr[stack[-1]] >= arr[i]:
                    stack.append(i)
                else:
                    tmp = 0
                    bottom = 0
                    while stack:
                        tmp = stack.pop()
                        if i - tmp == 1:
                            bottom = arr[tmp]
                        if i - tmp > 1:
                            ret += (i-tmp-1) * (min(arr[i], arr[tmp]) - bottom)
                            bottom = arr[tmp]
                        if bottom >= arr[i]:
                            stack.append(tmp)
                            break
                    stack.append(i)
            else:
                stack.append(i)
        return ret

发表于 2022-10-01 18:31:22 回复(0)
Python3
牛客48457647号头像 牛客48457647号
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#我认为这算法逻辑最优解了
class Solution:
    def maxWater(self , arr ):
        s = 0
        left = 0
        right = len(arr) - 1
        mark = min(arr[left],arr[right])
        while(left < right):
            if arr[left]<arr[right]:
                left += 1
                if arr[left]<mark:
                    s += mark - arr[left]
                else:
                    mark = min(arr[right],arr[left])
            else:
                right -= 1
                if arr[right] < mark:
                    s += mark - arr[right]
                else:
                    mark = min(arr[left],arr[right])
        return s
        
发表于 2021-09-21 17:43:45 回复(0)
Python3
龙驹寨镇做题家头像 龙驹寨镇做题家
python版本翻译自 评论区 【别卷啦 】大佬的方法。
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
import math
class Solution:
    def maxWater(self , arr ):
        # write code here
        n = len(arr)
        if arr is None or n<3:
            return 0
        l=0
        r = len(arr)-1
        area = 0
        min_num = min(arr[l],arr[r])
        while l<r:
            if arr[l]<arr[r]:
                l+=1
                if arr[l]<min_num:
                    area += min_num - arr[l]
                else:
                    min_num = min(arr[r],arr[l])
            else:
                r = r-1
                if arr[r]<min_num:
                    area += min_num - arr[r]
                else:
                    min_num =  min(arr[r],arr[l])
        return area
                   
发表于 2021-09-11 11:25:59 回复(0)
Python3
胡洪滔头像 胡洪滔 
可惜牛客的Python没有numpy这个模块
import numpy as np
class Solution:
    def maxWater(self , arr ):
        TotalRightRain=0
        TotalLeftRain=0
        arr=np.array(arr)
        if arr.argmax()!=len(arr)-1:
            right=arr[(arr.argmax()+1):]
            while True:
                RightRainList = right[:right.argmax()]
                if right.argmax() == len(right) - 1:
                    if len(RightRainList) == 0:
                        break
                    for i in RightRainList:
                        TotalRightRain += right[right.argmax()] - i
                    break
                elif len(RightRainList) == 0:
                    right = right[right.argmax() + 1:]
                    continue
                else:
                    for j in RightRainList:
                        TotalRightRain += right[right.argmax()] - j
                    right = right[right.argmax() + 1:]
        if arr.argmax()==0:
            return TotalRightRain+TotalLeftRain
        else:
            left=arr[:arr.argmax()]
            while True:
                LeftRainList=left[:left.argmax()]
                if left.argmax() == len(left)-1:
                    left=left[:left.argmax()]
                    if len(left)==0:
                        break
                    continue
                elif len(LeftRainList)== 0:
                    for m in left[left.argmax():]:
                        TotalLeftRain+=left[left.argmax()]-m
                    break
                else:
                    for n in left[left.argmax():]:
                        TotalLeftRain += left[left.argmax()] - n
                    left=LeftRainList
            return TotalRightRain+TotalLeftRain

发表于 2021-07-29 15:29:06 回复(1)
Python3
Love华为头像 Love华为
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    
    def add_water(self, arr):
        water = 0
        high = arr[0]
        for i in range(1, len(arr)):
            water += high - arr[i]
        return water
    
    def search(self, arr):
        self.p_f = 0
        fst = arr[0]
        water = 0
        for i in range(1, len(arr)):
            if arr[i] >= fst:
                water += self.add_water(arr[self.p_f:i])
                self.p_f = i
                fst = arr[i]
        return water
    
    def maxWater(self , arr ):
        # write code here
        total_water = self.search(arr)
        if self.p_f != len(arr)-1:
            res_arr = arr[self.p_f:len(arr)][::-1]
            total_water+=self.search(res_arr)
        return total_water
发表于 2021-07-17 22:17:20 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

接雨水问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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