11.Container With Most Water

水最多的容器问题

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i th line are (i, 0) and (i, height[i]).
给定一个长度为n的整数数组height，有n个向量，端点分别是(i，0)和(i，height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.
找出两条向量，他们之间和x轴，组成一个容器。找出这个容器的最大体积。

Return the maximum amount of water a container can store.
返回最大体积

Notice that you may not slant the container.
容器无法倾斜

思考

思考一

最简单的办法就是循环嵌套，两两组合，然后计算体积，比较并返回最大的。
但是这样很明显不妥。

思考二

可以从最高的向量开始，每次找他离他最远的等高或者比他高的向量，进行计算。
难点是，怎么判断距离这根向量最远的一根已经遍历的向量是哪一根。
任务分割一下：

1. 一个寄存器存储，当前有哪几个已经遍历过的向量。
2. 从寄存器里面找出距离当前遍历向量最远的向量。
3. 计算并比较，记录最大值。
   这里面任务的难点就是如何找最远的向量。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        sorted_h = sorted(height, reverse=True)
        tmp = []
        vol = 0
        for i in range(len(height)):
            index = -1
            while 1:
                if sorted_h[i] not in height[index+1:] or index >= len(height):
                    break
                index = height.index(sorted_h[i], index+1)
                tmp.append(index)
                
                for j in range(len(tmp)):
                    vol = max(vol, sorted_h[i]* abs(index-tmp[j])))
        return vol
        

自己写的很显然又超时了。效率不高（看到数组长度的取值范围我就想到这种可能性了）。怪不得别人都说，自己写的不会有别人写的好。

答案解析

暴力法

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

这是官方给的java的暴力破解法，果然超时了，我就说看着还没我的效率好，为什么会能通过。

双指针法

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
}

双指针法应该属于重头戏。
定义两个指针，分别表示左和右。当然循环条件就是右边的要一直在右边，左边的一直在左边。
然后通过l 和 r两个指针指向的向量，进行计算并比较，找出最大值。
但是我不是很懂，为什么这样一定可以找到最大值。
我用python再实现一遍。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        vol=0
        l=0
        r = len(height)-1
        tmp=0
        
        while l<r:
            lens = r-l
            if height[r]>height[l]:
                tmp = height[l]
                l+=1
            else:
                tmp = height[r]
                r-=1
                
            vol = max(vol, tmp * lens)
        return vol

为什么用这种算法呢？
由于面积是有两个height最小的一个和两个向量在x轴上的距离相乘计算而成的。
我们在已知距离的基础上，让距离逐渐缩短，然后改变较短的指针，让下一次容积可能会变得更大。
感觉有点像每次用最高的height和其他相乘。

但是我总觉得这种双指针法还是会漏去一些情况。。。可能是因为我习惯遍历了吧。

总结

双指针算法类似于滑动窗口，可以用双指针解决和滑动窗口里面内容有关的问题。
还是有点迷迷糊糊的，感觉。