双指针：从「LC11 盛最多水的容器」到「LC42 接雨水」

LC11 盛最多水的容器
选择两条线，它们与x轴构成的容器可以盛的水量取决于两条线中较短的那条以及两条线之间的距离。

朴素的思想是使用i和j遍历height中的所有线，但是这样的时间复杂度是$O(n^2)$。

我们让i从0开始，j从n-1开始，组成一个容器。

不妨假设height[0]<=height[n-1]，则固定左端点组成的所有容器中，无论右端点在哪，容器的盛水高度不可能高过左端点的线高，故初始容器就是固定左端点组成的所有容器中盛水量最多的容器。这里本质上把固定左端点对右端点进行$O(n)$的扫描通过分析变成了$O(1)$。

i=0的情况看完了，接下来应该移动左端点i。这里本质上是在固定右端点对左端点进行扫描。我们将左端点移动到比初始线高更高的第一个位置，则组成容器的盛水高度会变高，才有可能盛水量更多。则容器左端点从初始的i=0到现在位置中的所有左端点，其右端点一直保持j=n-1，因为不需要扫描，对于这些左端点，移动右端点不会使得盛水量更多。这里的分析就是算法的时间复杂度下降的原因。我们只需要分析如何让容器向着盛水量可能变大的方向去变化，每次移动较矮侧的端点至下一个更高位置处即可。

最终容器的变化过程就是，每次让容器较矮的一侧变的更高，直到两个端点重合。这样时间复杂度就是左右端点共同扫描完原数组，即$O(n)$。

这里我们对完备性进行一些简单证明。我们算法移动左右端点的过程中不会固定某一个端点对另一个端点进行$O(n)$的扫描都是因为通过分析可知，当我们在移动一侧的过程中，没有移动的那一侧无论取在哪也不会使得盛水量变大，所以盛水量最多的情形只要其左端点或者右端点作为过我们算法移动过程中的对应左端点或右端点，则我们的算法一定会得到不小于盛水量最多情形的结果。而由于那又是盛水量最多的情形，所以不小于即为等于。

class Solution {
    public int maxArea(int[] height) {
        int left=0,right=height.length-1,ans=0;
        while(left<right){
            ans=Math.max(ans,Math.min(height[left],height[right])*(right-left));
            if(height[left]<=height[right]){
                int std=height[left];
                //让left向右移动到一个更高的位置
                for(;left<right;left++){
                    if(height[left]>std) break;
                }
            }else{
                int std=height[right];
                //让right向左移动到一个更高的位置
                for(;right>left;right--){
                    if(height[right]>std) break;
                }
            }
        }
        return ans;
    }
}

这里的i和j就是双指针，从两侧向中间收拢，每次变化都向着可能使得盛水量变大的方向变化，且每次变化的特点是容器的盛水高度更高，宽度更小。这一题的变化过程分析对LC42 接雨水的解题有帮助。

LC42 接雨水
这道题也可以一样使用从两侧向中间收拢的双指针。我们下图中的线实际是一个宽度为1的柱子，这里画图简化了。

我们记minH为当前两个端点柱子高度的较小值，一开始让i=0，j=n-1，lastH为地面高度为0。则初始状态可以计算出lastH到minH高度之间的雨水量。

不妨假设height[0]<=height[n-1]，则无论怎么移动右端点，i=0高于minH的部分都不会有雨水，这点和LC11中的容器很像。所以对于i=0的部分，不需要花费$O(n)$去遍历右端点j，这时应该直接移动左端点i至下一个更高的柱子处，找到积水高度更高的“容器”。找到后，更新minH的值，并将原本minH的值给lastH，计算雨水量的增量是新的minH和最初minH即当前lastH之间的雨水，且容易反证在当前左端点左侧高于初始minH的部分不可能有雨水，这点和LC11中的容器也很像，因为该部分不属于新容器的范围。

这样我们一样是以$O(n)$的时间复杂度遍历了所有可能有雨水的左右端点情形，以朴素的思想，会在每个我们更新更高柱子的“容器”中遍历中间的每个宽度计算当前i到j宽度之间、当前lastH到minH高度之间的雨水量，这样总时间复杂度是$O(n^2)$，不是最优。

接下来需要再利用一定的分析技巧去降低时间复杂度，我们不要在每次“容器”改变形状时去遍历宽度计算雨水。我们有如下发现，以我们的左端点来看，我们会让左端点i从0变化到下一个更高柱子处，然后继续到下一个更高的柱子处，所有的雨水不会出现在每一个更高的柱子处，只会出现在我们移动左端点前后的中间的柱子处，且雨水高度也均为移动前的minH。所以我们有更聪明的计算雨水的方法，每次移动端点时，计算该端点处的雨水量（minH-height[i]，以左端点为例），而不再每次去遍历宽度计算“容器”内的lastH到minH高度之间的雨水量。这样总时间复杂度就被优化至$O(n)$。

class Solution {
    public int trap(int[] height) {
        int n=height.length,i=0,j=n-1;
        int minH,ans=0;
        while(i<j){
            minH=Math.min(height[i],height[j]);
            //i和j处较矮者向中间移动，移动至更高处停止
            //每次移动，计算移动的那个宽度的雨水量
            if(height[i]<=height[j]){
                for(;i<j&&height[i]<=minH;i++){
                    ans+=minH-height[i];
                }
            }else{
                for(;i<j&&height[j]<=minH;j--){
                    ans+=minH-height[j];
                }
            }
        }
        return ans;
    }
}