Analysis of rainwater connection

Title Description

Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .

Example 1：

Input ：height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output ：6
explain ： Above is an array of [0,1,0,2,1,0,1,3,2,1,2,1] Height map of representation , under these circumstances , Can connect 6 Units of rain （ The blue part indicates rain ）.

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/trapping-rain-water
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method ： Double pointer

Maximum water intake at each location = The left and right pointer positions correspond to the current maximum height corresponding to the endpoint of the end with small height - The height of the current position

utilize left and right The pointer scans from both ends of the array .
Judge the water receiving volume and pointer movement conditions .
Always give priority to moving the pointer with small height of the left and right pointer positions .

Code

class Solution(object):
    def trap(self, height):
        """ :type height: List[int] :rtype: int """
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0
        while left < right:   // Calculate from the left and right ends 
            leftMax = max(leftMax, height[left])  // Update the maximum height of the left endpoint 
            rightMax = max(rightMax, height[right]) // Update the maximum height of the right endpoint 
            if height[left] < height[right]:   // Determine the size of the left endpoint and the right endpoint , Move the small end towards the middle 
                ans += leftMax - height[left]  // Calculate the maximum rainwater that can be connected to the left end point 
                left += 1
            else:
                ans += rightMax - height[right] // Calculate the maximum rainwater that can be connected to the right end 
                right -= 1
        return ans