[Leetcode] 接雨水（相向双指针）

可以直接移步大神的解题思路，非常详细 -> 盛最多水的容器 接雨水_哔哩哔哩_bilibili

11. 盛最多水的容器 https://leetcode.cn/problems/container-with-most-water/description/
42. 接雨水 https://leetcode.cn/problems/trapping-rain-water/description/

11. 盛最多水的容器

解题思路：求区域面积的最大值，矩形的面积取决于底和高，高度的最大值未知，底的最大值已知，所以可以从底边最大开始，即左右各一枚指针。而高度取决于更小的高度，提高更小的高度才有可能找到更大的面积，所以哪边低哪边的指针往中间走一步，如果面积更大则更新，直到左右指针相邻。

class Solution:def maxArea(self, height: List[int]) -> int:n = len(height)left = 0right = n-1maxarea = 0while left < right:area = min(height[left],height[right]) * (right - left)maxarea = max(maxarea,area)if height[left] < height[right]:left += 1else:right -= 1return maxarea

42.接雨水

想破了脑袋，把局部最大值都拿出来然后没有覆盖“高-低-高”这种情况，而低本身可以是各种组合，其实如果能想到一侧的最大值挡着水就不会流出去就思路通畅了，这样高度就取决于另一边。

解题思路：计算每个位置的水量，取决于往左边看最高的柱子高度，以及往右边看最高的柱子高度，两者之间的较小者。即使相邻的左（右）侧柱子更低，因为更左（右）侧有更高的柱子，水不会流出去。

方法一：前缀最大值列表和后缀最大值列表

创建一个前缀列表，for循环从左往右，记录每个位置左侧已出现过的柱子的最大高度；

创建一个后缀列表，for循环从右往左，记录每个位置右侧已出现过的柱子的最大高度；

在每个位置比较上述两个值谁更小，把该位置的水量加到总和中。

class Solution:def trap(self, height: List[int]) -> int:ans = 0n = len(height)pre_max = [0]*nsuf_max = [0]*npre_max[0] = height[0]suf_max[-1] = height[-1]for i in range(1,n):pre_max[i] = max(pre_max[i-1],height[i])for i in range(n-2,-1,-1):suf_max[i] = max(suf_max[i+1],height[i])for i in range(n):ans += min(pre_max[i],suf_max[i]) - height[i]### Or use zip()# for pre,suf,h in zip(pre_max,suf_max,height):#     ans += min(pre,suf) - hreturn ans

方法二：相向双指针

相比于方法一使用更少内存，不用两个列表，改用两个变量。

指针1从左往右，记录左半边已出现的最高柱子；

指针2从右往左，记录右半边已出现的最高柱子；

一开始，指针1在最左侧，指针2在最右侧，哪半边的最高柱子的高度更小则该位置水量高度已确定（另一侧的最大值保证了水不会流出去），水量记入总和，该侧指针往中间移动一步，就这样直到两边的指针重合。

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