11. 盛水最多的容器 （双指针解）

原题：

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water

---

解题思路：

这道题利用双指针+动态规划的思想很容易就可以解出。

1.分别设置一头head，一尾tail，分别从头尾两端往中间遍历。

2.当height[head] < height[tail]时，head += 1; 反之 tail -= 1

3.利用木桶效应原理，取板短的那一个计算面积。

4.利用动态规划思想，计算每次的面积与之前最大的面积进行比较，得出新的最大的面积

5.head > tail 表示比较结束，跳出循环

---

代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 双指针，一头一尾,从两头开始比较
        lens = len(height)
        head = 0
        tail = lens-1
        max_area = (tail-head) * min(height[head],height[tail])
        while head < tail:
            if height[head] < height[tail]:
               head += 1
            else:
               tail -= 1
            max_area = max(max_area, min(height[head],height[tail])*(tail-head))
        return max_area