42.md

题目地址

https://leetcode-cn.com/problems/trapping-rain-water/

解答1

class Solution:
    def trap(self, height: List[int]) -> int:
        """
            接雨水

            给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
            输入: [0,1,0,2,1,0,1,3,2,1,2,1]
            输出: 6

            动态规划, 非最优解
        """
        if not height:
            return 0

        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size

        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])

        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])

        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]

        return ans

解答2

def trap(height):
    """
        接雨水

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
        输入: [0,1,0,2,1,0,1,3,2,1,2,1]
        输出: 6

        使用栈，非最优解
    """
    ans, current = 0, 0
    st = []
    while current < len(height):
        while st and height[current] > height[st[-1]]:
            top = st.pop()
            if not st:
                break
            distance = current - st[-1] - 1
            bounded_height = min(height[current], height[st[-1]]) - height[top]
            ans += distance * bounded_height

        st.append(current)
        current += 1
    return ans

解答3

def trap(height):
    """
        接雨水

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
        输入: [0,1,0,2,1,0,1,3,2,1,2,1]
        输出: 6

        动态规划
    """
    ans, left, right, left_max, right_max = 0, 0, len(height) - 1, 0, 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                ans += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                ans += right_max - height[right]
            right -= 1

    return ans

解答4

def trap(height):
    """
        接雨水

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
        输入: [0,1,0,2,1,0,1,3,2,1,2,1]
        输出: 6

        非最优解
    """
    if len(height) <= 1:
        return 0

    max_height = 0
    max_height_index = 0

    # 找到最高点
    for i in range(len(height)):
        h = height[i]
        if h > max_height:
            max_height = h
            max_height_index = i

    area = 0

    # 从左边往最高点遍历
    tmp = height[0]
    for i in range(max_height_index):
        if height[i] > tmp:
            tmp = height[i]
        else:
            area = area + (tmp - height[i])

    # 从右边往最高点遍历
    tmp = height[-1]
    for i in reversed(range(max_height_index + 1, len(height))):
        if height[i] > tmp:
            tmp = height[i]
        else:
            area = area + (tmp - height[i])

    return area