原视频链接：盛最多水的容器 接雨水【基础算法精讲 02】，博主：灵茶山艾府

一、盛最多水的容器（11. 盛最多水的容器）

左右两个指针分别在最左端和最右端，哪个所指向的高度短，就移动哪条；

在移动之前，计算一下此时的盛水量，如果比之前的答案大，就更新答案。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 时间复杂度O(n)
        # 空间复杂度O(1)
        ans = 0
        left = 0
        right = len(height) - 1
        while left < right:
            area = (right - left) * min(height[left], height[right])
            ans = max(area, ans)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans

二、接雨水（42. 接雨水）

方法一：前后缀分解

用pre_max数列来存储从左向右遍历的前缀最大值，suf_max数列来存储从右向左遍历的后缀最大值，例如：

height =     [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

pre_max = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]        (从左向右)

suf_mqx = [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]      （从右向左）

因为盛水量只能根据两板之间最短的高度来盛水，所以在pre_max与suf_max中取最小值再减去该位置height的值，就是这个位置的盛水量。

class Solution:
    def trap(self, height: List[int]) -> int:
        # 时间复杂度O(n)
        # 空间复杂度O(n)
        n = len(height)

        # 找前缀最大值数列
        pre_max = [0] * n # 创建大小为n的数组
        pre_max[0] = height[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i-1], height[i])
        
        # 找后缀最大值数列
        suf_max = [0] * n
        suf_max[-1] = height[-1]
        for i in range(n-2, -1, -1):
            suf_max[i] = max(suf_max[i+1], height[i])
        
        ans = 0
        for h, pre, suf in zip(height, pre_max, suf_max):
            ans += min(pre, suf) - h
        return ans

方法二：相向双指针

上述方法一的空间复杂度还有机会进行改进。

用指针从左右两端向中间进行移动，移动的过程中判断，如果左边的木板高度小于右边的木板高度，那么无论中间的木板有多高，左边木板所能盛的水量就是左边木板的高度减去左边指针该位置的高度。

class Solution:
    def trap(self, height: List[int]) -> int:
        # 时间复杂度 O(n)
        # 空间复杂度 O(1)
        n = len(height)
        ans = 0
        left, right = 0, n - 1
        pre_max, suf_max = 0, 0 # 这两个值在指针移动的过程中不断与height比较并进行更新

        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 += 1
            else: 
                ans += suf_max - height[right]
                right -= 1
        return ans