"""
two-pointers && slide-window

HARD：

42. 接雨水

"""

question_list = [42,]

"""
42. 接雨水
双指针对撞，左右分区分别进行计算。每次只计算当前列能接多少雨水，累计求和。
DP解法略深奥，与模版有点冲突，忽略。
"""
def trap(self, height):
    """
    1.还是指针对撞，每次移动矮的。高的作为移动指针围起来区域的另一个边不能动，所以要移动矮的。
    2.按列累计求和，每次只计算当前列。
    3.因为指针对撞，所以框架不变，还是以左右指针对比进行条件的区分，分别计算。
    """
    left, right = 0, len(height) - 1
    max_left_height, max_right_height = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            cur_height = height[left]
            if cur_height < max_left_height:
                water += max_left_height - cur_height
            else:
                max_left_height = cur_height
            left += 1
        else:
            cur_height = height[right]
            if cur_height < max_right_height:
                water += max_right_height - cur_height
            else:
                max_right_height = cur_height
            right -= 1
    return water