接雨水

LeetCode 第42题

问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

本题的核心思路是，如果柱子之间能积水，那么它必然是一个凹槽。可以使用双向指针分别指向数组的首尾（假设为left和right)，如果left < right，则向右逼近，如果中间遇到凹点，则表示能积水，如果遇到凸点，则更新左侧最大的门阀，然后继续向右逼近。同理left <= right

Code

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        # 分别执行首尾
        left, right = 0, len(height) - 1

        # 左侧和右侧的最大门阀
        leftmax, rightmax = 0, 0
        
        trap_sum = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] < leftmax:
                    # 遇到凹点
                    trap_sum += leftmax - height[left]
                else:
                    # 遇到凸点，更新门阀大小
                    leftmax = height[left]
                left += 1
            else:
                if height[right] < rightmax:
                    trap_sum += rightmax - height[right]
                else:
                    rightmax = height[right]
                right -= 1
        
        return trap_sum