Problem: 42. 接雨水

思路 & 解题方法

前缀后缀应该是最容易想到的方法了，双指针需要多理解一下。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

前缀后缀

class Solution:def trap(self, height: List[int]) -> int:length = len(height)pre, rear = [0] * length, [0] * lengthfor i in range(1, length):pre[i] = max(pre[i - 1], height[i - 1])for i in range(length - 2, -1, -1):rear[i] = max(rear[i + 1], height[i + 1])ans = 0for i in range(1, length - 1):ans += max(0, min(pre[i], rear[i]) - height[i])return ans

双指针

class Solution:def trap(self, height: List[int]) -> int:length = len(height)pre_max, rear_max = 0, 0left, right = 0, length - 1ans = 0while left < right:pre_max = max(pre_max, height[left])rear_max = max(rear_max, height[right])if pre_max < rear_max:ans += pre_max - height[left]left += 1else:ans += rear_max - height[right]right -= 1return ans