hot100 11.盛水最多的容器

思路：这道题无法使用分治法和动态规划法，要想得到O(n)的解法只能使用双指针。

1.本题中双指针的含义：指针每一次移动，都意味着排除掉了一个柱子。

2.举例：

（1）如下图所示，在一开始考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离d = 8，水的高度取决于两根柱子之间较短的那个，即左边柱子的高度h = 3。因此水的面积为3×8=24。

（2）如果选择固定一根柱子，另外一根变化，水的面积会如何变化？

（a）当前柱子是最两侧的柱子，水的宽度d为最大，其他的组合水的宽度都比这个小。

（b）左边的柱子较短，决定了水的高度为3。如果移动左边的柱子，新的水面高度不确定，但一定不会超过右边柱子的高度7。

（c）如果移动右边的柱子，新的水面高度一定不会超过左边柱子的高度3，也就是不会超过现在水面的高度。

（3）过程推导：

（a）由（2）推理可知，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。因此左边柱子和任意一个其他柱子的组合都可以排除了。因此可以排除掉左边的柱子了。

（b）同理，若右边的柱子更小，那么右边柱子和任意一个其他柱子的组合都可以排除了。因此可以排除掉右边的柱子了。

（c）随着不断的排除，i和j都会往中间移动，当i和j相遇时，算法就结束了。

3.图解双指针解法的原理：

（1）排除掉一根柱子，指针移动究竟代表着什么？

假设一共有n根柱子，编号0，1，...，n - 1。高度分别为H0、H1、...、Hn - 1。要寻找的是两根柱子i,j，它们需要满足的约束条件是：

——i、j都是合法的柱子下标，即0<=i<n，0<=j<n。

——i在j的左边，即i < j。

（2）希望从中找到容纳水面积最大的柱子（i,j），以n = 8为例，这时候全部的搜索空间为：

（3）由于i、j的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间大小是O(n^2)数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是O(n^2)。要想得到O(n)的解法，就需要能够一次排除多个单元格。

（4）一开始，先检查右上方的单元格（0,7），即考虑最左边的0号柱子和最右边的7号柱子，计算它们之间容纳水的面积，然后比较一下两根柱子的高度，关注其中较短的一根。

（5）假设左边的0号柱子较短，根据推理，0号柱子目前的水面高度已经到了上限。因此排除0号柱子的情况，也就是i = 0的情况，对应i++，就是削减了一行的搜索空间。

（6）排除了搜索空间的一行后，剩余的搜索空间仍然是倒三角形状。检查右上方的单元格（1,7），即考虑1号柱子和7号柱子，计算它们之间容纳水的面积。然后，比较两根柱子的高度。

（7）假设此时7号柱子较短，此时要排除7号柱子的情况，对应j--，就是削减了一列的搜索空间。

（8）经过n步后，就能排除掉所有的搜索空间，检查完所有的可能性。

附代码：

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