首页 > 试题广场 >

接雨水问题

[编程题]接雨水问题

热度指数：92101 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：数组长度 $0 \le n \le 2\times10^5$ ，数组中每个值满足 $0 < val \le 10^9$ ，保证返回结果满足 $0 \le val \le 10^9 \$

要求：时间复杂度 $O(n)$

示例1

输入

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

输出

说明

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

示例2

输入

[4,5,1,3,2]

输出

算法知识视频讲解

Python 3

牛客344707077号

#
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        if not arr:
            return 0
        if len(arr)<3:
            return 0
        low = 0 # 指针
        high = len(arr)-1 #指针
        maxl = 0 # 左边指针所经的最高高度
        maxr = 0 # 右边指针所记录到的最高高度
        output = 0
        while low < high:
            maxl = max(maxl, arr[low])
            maxr = max(maxr, arr[high])
            if maxr > maxl:
                output += maxl-arr[low]
                low += 1
            else:
                output += maxr-arr[high]
                high -= 1
        return output

发表于 2022-05-30 16:16:09 回复(0)

Python 3

Vivimore

双指针
时间复杂度：O(n) 空间复杂度：O(1)

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        if len(arr) == 0:
            return 0
        res = 0
        left = 0
        right = len(arr) - 1
        max_l = 0
        max_r = 0
        while left < right:
            max_l = max(max_l, arr[left])
            max_r = max(max_r, arr[right])
            if max_l > max_r:
                res += max_r - arr[right]
                right -= 1
            else:
                res += max_l - arr[left]
                left += 1
        return res

发表于 2022-05-27 15:13:23 回复(0)

Python 3

Virtual~

class Solution:
    def maxWater(self, arr: List[int]) -> int:
        # write code here
        n = len(arr)
        
        L_height = [0] * n
        R_height = [0] * n
        
        L_height[0] = arr[0]
        R_height[n-1] = arr[n-1]
        
        # 从左往右记录L的高度
        for i in range(1, n):
            L_height[i] = max(arr[i], L_height[i-1])
        
        # 从右往左记录R的高度
        for i in range(n-2, -1, -1):
            R_height[i] = max(arr[i], R_height[i+1])
        
        waters = 0
        # 记录答案， 答案 = 左右两边柱子的最小值-当前位置的高度
        for i in range(1, n-1):
            water = min(L_height[i], R_height[i]) - arr[i]
            waters += max(0, water)
        
        return waters

发表于 2022-04-17 10:48:46 回复(0)

Python 3

叶有几纹

很简单好用的方法，对于给的样例数据[3,1,2,5,2,4]，我们可以看到，因为第一个的高度是3，以3为左边界，那么后面的后可以加水加到3。例如这里3后面的1和2都可以加到3，直到碰到新的最高点5
然后以5为新的起点，以此把后面的加到5，我们得到的新序列为[3,3,3,5,5,5]，但是这里有一个问题，原数列的最右边没有比5更大的了，无法封住最右边两个添加到5的序列，应该怎么办？很简单，我们分别从左到右，从右到左计算一个，从左到右为[3,3,3,5,5,5]，从右到左为[5,5,5,5,4,4]，然后对这两个序列取最小值即得到[3,3,3,5,4,4]，这就是我们想要求得的结果

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here      
        n = len(arr)
        if (n < 3):
            return 0
        num_left = [0 for i in range(n)]
        num_right = [0 for i in range(n)]
        num = [0 for i in range(n)]
        
        r1 = 0
        r2 = 0
        #分别从左到右 和 从右到左
        for i in range(n):
            if (arr[i] > r1):
                r1 = arr[i]
            num_left[i] = r1
            if (arr[n-1-i] > r2):
                r2 = arr[n-1-i]
            num_right[n-1-i] = r2
        
        for i in range(n):
            num[i] = min(num_left[i], num_right[i])
            
        return (sum(num) - sum(arr))

发表于 2022-04-15 14:05:57 回复(0)

Python 3

牛客296365098号

为什么要用双指针，就不能先求完左侧的，再去求右侧的吗？

    def maxWater(self , arr: List[int]) -> int:
        # write code here
        
        highest = max(arr)
        highest_ind = arr.index(highest)
        
        water = 0
        left = arr[0]
        for i in range(1, highest_ind):
            if arr[i] < left:
                water += left - arr[i]
            else:
                left = arr[i]
        
        right = arr[-1]
        for i in range(len(arr)-1, highest_ind, -1):
            if arr[i] < right:
                water += right - arr[i]
            else:
                right = arr[i]
                
        return water

发表于 2022-03-06 22:35:39 回复(0)

Python 3

牛客318213606号

# 双指针
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        n=len(arr)
        L=1
        R=n-2
        maxL,maxR=arr[0],arr[n-1]# 左侧/右侧的最大值
        res=0
        while L<=R:
            if maxL<maxR:
                t=maxL-arr[L]
                if t>0:
                    res+=t
                maxL=max(maxL,arr[L])
                L+=1
            else:
                t=maxR-arr[R]
                if t>0:
                    res+=t
                maxR=max(maxR,arr[R])
                R-=1
        return res

发表于 2022-02-23 16:43:46 回复(1)

Python 3

牛客114920445号

双指针，python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
# 左成云算法课讲的解法
class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        left_most = 0
        right_most = len(arr)-1
        # 双指针，初始指针第一个位置，和最后一个位置，这两个位置不可能装水，设为初始左右边界
        water = 0
        while left_most < right_most: # 当两个指针相遇，循环结束
            #判断两端的指针所对应的柱子哪个矮一些，矮的为短板，决定最多接多少雨水
            #如果左边的较小，用一个cur指针指向左边位置加一，如果cur指针位置小于左
            #边的边界，则可计算雨水数目，arr[left_most]-arr[cur]，因为此时的局限
            #在左边，如果cur位置高于左边界，更新左边界，进入外层大循环
            if arr[left_most] <= arr[right_most]: 
                cur = left_most+1
                while arr[cur] < arr[left_most]:
                    water += arr[left_most] - arr[cur]
                    cur+=1
                left_most = cur 
            # 右边界为短板，同上一样的算法
            else:
                cur = right_most-1
                while arr[cur] < arr[right_most]:
                    water += arr[right_most] - arr[cur]
                    cur -= 1
                right_most = cur 
        return water

发表于 2022-02-13 22:12:52 回复(0)

Python 3

江西南昌陈彬

代码提交成功平均运行耗时 450 毫秒左右

1.首先求数组最大值a，定位索引位置；

2.根据最大值左右两边拆分数组，求左右两边数组最大值分别为多少，

3.左右两边最大值与数组最大值a之间的差值就是雨水；

4.同理循环上述即可；

# -*- coding:utf-8 -*-
def max_yu(list_yu):
    max_n = 0
    i = 0
    max_zhu_inedx = []
    len_n = len(list_yu)
    max_zhu = max(list_yu)
    max_zhu_wzhi_c = list_yu.index(max_zhu)
    max_zhu_count = list_yu.count(max_zhu)
    if max_zhu_count == 1 and list_yu.count(list_yu[0]) == len_n-1:
        print(max_n)
        return max_n
    else:
        if max_zhu_count > 1:
            while i < len_n:
                if max_zhu == list_yu[i]:
                    max_zhu_inedx.append(i)
                i += 1
            min_zhu_index = min(max_zhu_inedx)
            max_zhu_index = max(max_zhu_inedx)
            if max_zhu_index - min_zhu_index == 1:
                max_n = 0
            else:
                min_zhu_index_lshi = min_zhu_index
                while min_zhu_index_lshi < max_zhu_index:
                    max_n = max_n + max_zhu - list_yu[min_zhu_index_lshi]
                    min_zhu_index_lshi += 1
                chushi = max_zhu_index
                while chushi < len_n:
                    max_f1_list = list_yu[chushi + 1:]
                    if len(max_f1_list) != 0:
                        max_f1 = max(max_f1_list)
                        max_f1_inedx = max_f1_list.index(max_f1)
                        if max_f1_inedx == 0:
                            chushi += 1
                        else:
                            j = 0
                            while j < max_f1_inedx:
                                max_n = max_n + max_f1 - max_f1_list[j]
                                j += 1
                            chushi = max_f1_inedx + 1 + chushi
                    else:
                        chushi += 1
                chushi = min_zhu_index
                while chushi > 0:
                    max_f2_list = list_yu[:chushi]
                    max_f2 = max(max_f2_list)
                    max_f2_inedx = max_f2_list.index(max_f2)
                    if max_f2_inedx == len(max_f2_list) - 1:
                        chushi -= 1
                    else:
                        j = max_f2_inedx
                        while j < len(max_f2_list):
                            max_n = max_n + max_f2 - max_f2_list[j]
                            j += 1
                        chushi = max_f2_inedx
                return max_n


        else:
            max_zhu_inedx.append(max_zhu_wzhi_c)
        if len(max_zhu_inedx) == 1:
            chushi = max_zhu_wzhi_c
            while chushi < len_n:
                max_f1_list = list_yu[chushi+1:]
                if len(max_f1_list) != 0:
                    max_f1 = max(max_f1_list)
                    max_f1_inedx = max_f1_list.index(max_f1)
                    if max_f1_inedx == 0:
                        chushi += 1
                    else:
                        j = 0
                        while j < max_f1_inedx:
                            max_n = max_n + max_f1 - max_f1_list[j]
                            j += 1
                        chushi = max_f1_inedx + 1 + chushi
                else:
                    chushi += 1
            chushi = max_zhu_wzhi_c
            while chushi > 0:
                max_f2_list = list_yu[:chushi]
                max_f2 = max(max_f2_list)
                max_f2_inedx = max_f2_list.index(max_f2)
                if max_f2_inedx == len(max_f2_list) - 1:
                    chushi -= 1
                else:
                    j = max_f2_inedx
                    while j < len(max_f2_list):
                        max_n = max_n + max_f2 - max_f2_list[j]
                        j += 1
                    chushi = max_f2_inedx
            return max_n

max_yu([3,1,2,5,2,4]  )

发表于 2022-02-09 13:11:37 回复(0)

Python 3

Joy_9

class Solution:
    def trap(self, height: List[int]) -> int:
        #双指针优化
        s,left_wall,right_wall=0,0,0
        left,right=0,len(height)-1
        while left<right:
            left_wall=max(left_wall,height[left])
            right_wall=max(right_wall,height[right])
            if  left_wall<right_wall:
                s+=left_wall-height[left]
                left+=1
            else:
                s+=right_wall-height[right]
                right-=1
        return s
        
        #暴力解法
        # s=0
        # for i in range(1,len(height)-1):
        #     if min(max(height[:i]),max(height[i+1:]))>height[i]:
        #         v=min(max(height[:i]),max(height[i+1:]))-height[i]
        #         s+=v
        # return s
        #转换为一个类似岛屿问题时间超过限制
        # m=max(height)
        # n=len(height)
        # v=0
        # dp=[[0]*n for _ in range(m)]
        # for i in range(m):
        #     dp[i][0]=0
        #     dp[i][n-1]=0
        # for i in range(m):
        #     for j in range(1,n-1):
        #         if  height[j]<m-i and height[j]<=max(height[j+1:]) and ((height[j]<=height[j-1] and height[j-1]>=m-i)&nbs***bsp;dp[i][j-1]==1) and max(height[j+1:])>=m-i:
        #             dp[i][j]=1
        #             v+=1
        #         else:
        #             dp[i][j]=0
        # return v

发表于 2022-01-24 04:41:22 回复(0)

Python 3

牛客969630771号

class Solution:
    def maxWater(self , arr ):
        # write code here
        start = arr[0]
        end = arr[-1]
        top = max(arr)
        n = len(arr)
        water = n*top-sum(arr)
        for i in range(n):
            if arr[i] < top and arr[i] <=start:
                water -= top-start
            elif arr[i] < top and arr[i] > start:
                start = arr[i]
                water -= top - start
            elif arr[i] == top:
                break
        for j in reversed(range(n)):
            if arr[j] < top and arr[j] <=end:
                water -= top-end
            elif arr[j] < top and arr[j] > end:
                end = arr[j]
                water -= top - end
            elif arr[j] == top:
                break
        return water

发表于 2021-09-08 10:45:39 回复(0)

Python 3

可恶，被他装到了

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
def maxWater(self , arr ):

return self.HowmuchWater(arr)

def HowmuchWater(self, arr):
if len(arr) < 2:
return 0
else:
result = 0
left, right = None, None
left_index, right_index = 0, 0
for index_i,i in enumerate(arr):
if left == None or (right == None and i >= left):
left = i
left_index = index_i
elif right == None:
right = i
right_index = index_i
else:
if i >= left:
right = i
right_index = index_i
break
elif i >= right:
right = i
right_index = index_i
for j in arr[left_index+1:right_index]:
result += min(left,right) - j
return result + self.HowmuchWater(arr[right_index:])


# write code here

发表于 2021-08-26 17:29:16 回复(0)

Python 3

清华李坤

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
def maxWater(self , arr ):
# write code here
ans=h1=h2= 0
for i in range(len(arr)):
h1 = max(h1,arr[i])
h2 = max(h2,arr[-i-1])
ans = ans + h1 + h2 -arr[i]
return ans - len(arr)*h1

发表于 2021-08-24 22:48:32 回复(0)

Python 3

牛客944262486号

class Solution:
    def maxWater(self , arr ):
        # write code here
        cnt, left, right = 0, 0, len(arr)-1
        while left < right:
            minn = min(arr[left], arr[right])
            while left < right and arr[left] <= minn:
                cnt += minn - arr[left]
                left += 1
            while left < right and arr[right] <= minn:
                cnt += minn - arr[right]
                right -= 1
        return cnt

发表于 2021-08-14 21:32:53 回复(0)

Python 3

临江仙9

我的有一个排序操作

class Solution:
def maxWater(self , arr ):
# write code here
N = len(arr)
if N < 2:
return 0
sorted_index = [x for x,y in sorted(enumerate(arr), key = lambda x: -x[1])]
left = 0
right = 0
if sorted_index[0] == 0:
pass
elif sorted_index[0] == N-1:
left = N-1
right = N-1
else:
left = sorted_index[0]
right = sorted_index[0]
result = 0
for k in sorted_index[1:]:
if k < left:
for m in range(k+1,left):
result += arr[k] - arr[m]
left = k
if k > right:
for m in range(right+1,k):
result += arr[k] - arr[m]
right = k
if left == 0 and right == N-1:
return result

发表于 2021-08-07 15:55:05 回复(0)

Python 3

牛客152785677号

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr ):
        top = arr.index(max(arr))
        list_1 = arr[0:top+1]
        list_2 = arr[top::]
        list_2 = list_2[::-1]
        list_s = [list_1,list_2]
        num_c = 0
        for elist in list_s:
            num_s = elist[0]
            for i in range(len(elist)):
                if 0<i<len(elist)-1:
                    num_e = elist[i]
                    if num_s > num_e:
                        num_c += num_s-num_e
                    else:
                        num_s = num_e
        return num_c

发表于 2021-08-06 22:36:15 回复(0)

提交观点

问题信息

动态规划单调栈双指针

难度：

24条回答 1119收藏 9927浏览

通过挑战的用户

black__t

2023-01-12 23:52:11
譞

2022-11-03 20:27:16
牛客65523...

2022-10-05 21:51:23
Brilley

2022-09-21 18:14:00
灰度值为零

2022-09-20 14:46:14

接雨水问题

输入

输出

说明

输入

输出

代码提交成功平均运行耗时 450 毫秒左右

问题信息

热门推荐

通过挑战的用户

相关试题

接雨水问题

输入

输出

说明

输入

输出

代码提交成功平均运行 耗时 450 毫秒左右

问题信息

热门推荐

通过挑战的用户

相关试题

代码提交成功平均运行耗时 450 毫秒左右