leedcode：11. 盛最多水的容器(python实现)_容器最多的水python 单调栈

    大家最容易想到的算法就是直接暴力遍历所有的面积，最终选出一个最大值。当然对于中等难度的题目，时间复杂度肯定不能是O(n^2)这么简单，所以要对于题目进行分析。
    下面给出双指针的算法：设置两个指针left和right，分别指向数组最左边和最右边的元素。我们知道容器的面积 = 底*两边中的较短边。当指针这么设置的时候，底的长度已经达到最大了，下面我们就来减少底的长度，增加容器的高，也就是把两个指针向内侧移动。那么我们移动哪一边呢？标准是移动高较小的那一边，因为我们的容器的高是由较短边制约的，所以当我们移动较短边的指针，当遇到更长的边，才有可能改变目前容器的高度（不然如果移动较长边的指针，容器高度永远决定于较短的那个边不会改变）。当左右指针相等的时候，就停止循环，至此也就找到了最大的面积。
    从更加根本的角度分析双指针的思路，之所以能够这么去做，是因为容器的面积由底和高两个因素决定，而我们在一开始就已经能够找到最大的底边长度，所以才能够逐步地减少底边长度去探求更长的高。有种控制变量法的意味在里面了。所以说如果我们不知道底的最大长度的时候就不能采用这种方法了。

下面是用python实现的双指针代码：

class Solution:
    def maxArea(self, height) -> int:
        left = 0
        right = len(height) - 1
        area = 0
        while left != right:
            tmp = (right - left) * min(height[left], height[right])
            if tmp > area:
                area = tmp
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return area
1
2
3
4
5
6
7
8
9
10
11
12
13
14