接雨水问题

接雨水问题_牛客题霸_牛客网

问题简述

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

思路1

• 使用两个数组分别记录从左到右、从右到左的在当前位置的最大值；

  以 [3,1,2,5,2,4] 为例：
      L = [3,3,3,5,5,5]
      R = [5,5,5,5,4,4]
  则 ret = sum(min(L[i], R[i]) - arr[i] for i in range(N))

• 空间复杂度 O(N)；

• 遍历技巧，一次遍历同时生成 L 和 R；

Python

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        N = len(arr)
        l_mx = r_mx = float('-inf')
        L, R = [0] * N, [0] * N
        for i in range(N):
            l_mx = max(l_mx, arr[i])
            L[i] = l_mx
            r_mx = max(r_mx, arr[N - i - 1])
            R[N - i - 1] = r_mx

        ret = 0
        for i in range(N):
            ret += min(L[i], R[i]) - arr[i]
        return ret

思路2：双指针

• 在思路 1 的基础上利用双指针优化空间复杂度；

• 写法 1 和写法 2 都是在思路 1 的基础上优化；

• 写法 3 提供了一种全局的思路；

Python 写法1

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        
        N = len(arr)
        l, r = 0, N - 1  # 左右指针
        l_mx = r_mx = 0
        ret = 0
        while l < r:
            l_mx = max(l_mx, arr[l])
            r_mx = max(r_mx, arr[r])
            h = min(l_mx, r_mx)
            if h >= arr[l]:  # 必须 >= 
                ret += h - arr[l]
                l += 1
            else:
                ret += h - arr[r]
                r -= 1
        
        return ret

Python 写法2

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        N = len(arr)
        l, r = 0, N - 1  # 左右指针
        l_mx = r_mx = 0  # 左右最大值
        ret = 0
        while l < r:
            l_mx = max(l_mx, arr[l])
            r_mx = max(r_mx, arr[r])
            if l_mx < r_mx:  # < 或者 <= 都可以
                ret += l_mx - arr[l]
                l += 1
            else:
                ret += r_mx - arr[r]
                r -= 1
        return ret

Python 写法3

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        N = len(arr)
        l, r = 0, N - 1  # 左右指针
        # l_mx = r_mx = 0  # 左右最大值
        mxH = 0  # 当前最大桶高
        ret = 0
        while l < r:
            mxH = max(mxH, min(arr[l], arr[r]))
            if arr[l] < arr[r]:  # < 或者 <= 都可以
                ret += mxH - arr[l]
                l += 1
            else:
                ret += mxH - arr[r]
                r -= 1
            
        return ret