leetcode42 -- Trapping Rain Water (被面过)

leetcode42 -- Trapping Rain Water (被面过)

题目

42. Trapping Rain Water
Hard

3874

71

Favorite

Share
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6


题目的意思是问当下雨的时候,假设下的很大,这个能放多少水

解法1.

这个题目拿来的时候,首先想一下,什么时候当前的坐标会存水,这个比较明显,就是当这个坐标是个“盆地”的时候,也就是两边高,中间低的时候,就一定会存水,这个两边高不一定是与它最近的两个比它高,而是说它左边的最高的地方比它高,以及它右边的最高的地方也比它高,(写到这的时候,我抬头看看左右两边的天空.)

将左边的最高的如果记为”left_most”的话,右边最高的记为”right_most”的话,当前坐标的高度记为”height[i]”的话,那么只有当

“min(left_most, right_most) > height[i]”的时候,当前坐标才能够存住水,而且存水的量是”min(left_right, right_most)-height[i]”.

根据上面的解释,第一个version就可以写出来了.

class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        
        for i in range(1, len(height)):
            # find left_most and right_most
            left_most, right_most = 0, 0
            if i==0:
                left_most = 0
            else:
                left_most = max(height[:i])  # 不包括i
            if i == len(height)-1:
                right_most = 0
            else:
                right_most = max(height[i+1:])  # 不包括i
                
            add = min(left_most, right_most)-height[i]
            if add > 0:
                water += add      
        return water 

法二

上面的方法虽然可以,但是一看就是两个for,复杂度有些高, 那容易想到的就是拿空间换时间,即先遍历一遍数组,把最大,存起来.


class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        
        left_most = [0] * len(height)
        right_most = [0] * len(height)
        
        n = len(height)
        for i in range(1,n):
            if i ==1:
                left_most[1] = height[0]
            else:
                left_most[i] = max(height[i-1],left_most[i-1])
                
        for i in range(n-2,-1, -1):        
            if i == n-2:
                right_most[n-2] = height[-1]
            else:
                right_most[i] = max(height[i+1], right_most[i+1])
                
        
        for i in range(len(height)):
    
            add = min(left_most[i], right_most[i])-height[i]
            if add > 0:
                water += add      
        return water 
                

即先用两个列表把right_most和left_most给存起来,这样的话,复杂度就降成O(n)了,只是空间多了一些.

解法三,比较漂亮

仍然继续上面的思路,其实只要当前的位置是个两边高中间低的地方的话就能够存水,也就是说只要左边有比它高,右边有比它低的地方,那么这个地方就一定可以存水,之前是找到左边最高和右边最高来判断它能否存水,现在不需要判断最高的了,只需要判断有没有比它高的.

方法是双指针法.

class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        left_most, right_most = 0, 0
        
        left, right = 0, len(height)-1
        
        while left<right:
            if height[left] < height[right]:  # 这时候右边高了,如果要存水还要判断左边是不是也高
                if left_most > height[left]:  # 太好了,这种能存水
                    #water += min(left_most, height[right]) - height[left]
                    # 和下面的等效
                    water += left_most-height[left]
                    
                else:
                    # 不能存水,更新最大
                    left_most = height[left]
                    
                left += 1
            else:     # 说明左边可能高,那这时候判断右边
                if right_most > height[right]:
                    water += right_most - height[right]
                else:
                    right_most = height[right]
                    
                right -= 1
                
        return water 

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦