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

动态编程

python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left_max = [0] * size
        right_max = [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):
            ans += min(left_max[i], right_max[i]) - height[i]  # 本身有的一定高度需要减去
        return ans
print(Solution().trap([4, 2, 0, 3, 2, 5]))

双指针

python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left = 0
        right = size - 1
        left_max = 0
        right_max = 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
print(Solution().trap([4, 2, 0, 3, 2, 5]))