LeetCode

Appearance

42. Trapping Rain Water ​

题目 ​

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

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
Related Topics
  • 栈
  • 数组
  • 双指针
  • 动态规划
  • 单调栈

  • 👍 5716
  • 👎 0

    • 解法一 ​

    双重遍历法 寻找左侧墙，再去寻找右侧墙，这种算法的复杂度为 O(N2) 不符合题目要求，直接超时了

    • 左侧逻辑： 左侧高度大于下一个元素高度，即可为左侧墙
    • 右侧逻辑：
      • 若右侧大于左侧，可直接确定右侧墙
      • 若右侧一直小于左侧，则寻找右侧最大的最大高度
      • 下次的左墙可直接跳到最大高度开始
    python
    class Solution:
    def trap(self, height: List[int]) -> int:
        size = len(height)
        water = 0
        if size < 3:
            return 0

        left = 0

        while left < size - 2:
            if height[left] <= height[left + 1]:
                left += 1
                continue

            right  = left + 1
            max_right = right

            # 寻找右边最高的桶
            for i in range(right, size):
                if height[left] <= height[i]:
                    right = i
                    break
                if height[max_right] < height[i]:
                    max_right = i
            else:
                right = max_right


            bucket_height = min(height[right], height[left])

            water_list = [ max(0, bucket_height - h ) for h in height[left + 1: right]]
            water += sum(water_list)

            left = right

        return water

    解法二 ​

    双指针法, 整体看作一个水槽，左右同时对比，假设 height[left] < height[right]

    • 确定储水方向 -> 短边必可储水
    • 确定储水量 -> 储水量由最短的一边确定，最大容纳量短边最高的木板确定

    关键需要维护左侧最大和右侧最大值，小于当前最大的值的雨水都可被收集

    py
    from typing import List
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while left < right:
            if height[left] <= height[right]:
                if height[left] > left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] > right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1

        return water
        
# leetcode submit region end(Prohibit modification and deletion)

Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1])

    复杂度分析 ​

    • 时间复杂度O(N)
    • 空间复杂度O(1)