接雨水问题

[编程题]接雨水问题

热度指数：92095 时间限制：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

sjqg

class Solution:
    def maxWater(self , arr ):
        water=0
        max_arr_l=[arr[0]]*len(arr)#记录位置i处左侧的最大值
        max_arr_r=[arr[-1]]*len(arr)#记录位置i处右侧的最大值
        for i in range(1,len(arr)-1):
            max_arr_l[i]=arr[i-1] if arr[i-1]>max_arr_l[i-1] else max_arr_l[i-1]
        for i in reversed(range(1,len(arr)-1)):
            max_arr_r[i]=arr[i+1] if arr[i+1]>max_arr_r[i+1] else max_arr_r[i+1]
        for i in range(1,len(arr)-1):
            max_=min(max_arr_l[i],max_arr_r[i])
            if max_-arr[i]>0:
                water+=max_-arr[i]
        return water

发表于 2021-09-08 14:01:50 回复(0)

Python

牛客四二三号

题意与python题解

1、题意（题解区某大佬图）

与力扣 42.接雨水一致

2、python题解

①python牛客有问题，返回1都能超时。以下题解已通过本地IDE

②动态编程法：遍历两遍，从左往右遍历保存当前最大值，从右往左遍历保存当前最大值，然后容水量为两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。（题解区某大佬C++改写）

class Solution:
    def maxWater(self , arr ):
        # write code here
        le = len(arr)
        l = list([0] * le)
        r = list([0] * le)
        
        l[0] = arr[0]
        r[le - 1] = arr[le - 1]
        for i in range(1, le):
            l[i] = max(l[i - 1], arr[i])
            r[le - i - 1] = max(r[le - i], arr[le - i - 1])
        
        res = 0
        for i in range(1, le - 1):
            if min(l[i], r[i]) - arr[i] > 0:
                res += min(l[i], r[i]) - arr[i]
        return res

③双指针（力扣Java官解改写）

我们先明确几个变量的意思：

left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的 left：从左往右处理的当前下标 right：从右往左处理的当前下标

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标

class Solution:
    def maxWater(self, arr ):
        left, right, res, left_max, right_max = 0, len(arr) - 1, 0, 0, 0
        while left < right:
            if arr[left] < arr[right]:
                if arr[left] > left_max:
                    left_max = arr[left]
                else:
                    res += left_max - arr[left]
                left += 1
            else:
                if arr[right] > right_max:
                    right_max = arr[right]
                else:
                    res += right_max - arr[right]
                right -= 1
        return res

编辑于 2021-03-23 14:09:41 回复(1)