Container With Most Water (头尾指针的妙用)

 

   对于数组 A ， 怎么求的Max((j - i) * [min (A[i] , A[j])]) , 其中 i , j < A.length - 1

 

   这道题目， 暴力的话，很容易， O(n^2) , 可是采用头尾指针的方法可以在O(n)的时间内完成！

 

   O(n) 的代码 及其简单，就是头尾指针，谁小谁移动，然后，求两个指针间的面积，再更新

   最大面积即可。

 

   但是，为什么？为什么这个方法能行了？

   比如 ： 数组A[3 , 7 , 4 , 8 , 5]

   暴力的话，就是：

   3 7 3

   3 4 6

   3 8 9

   3 5 12

   7 4 4

   .....

   8 5 5

 

   观察上面的可以知道：

   以A[0] = 3 为一条边的话，那么高度最大为3 ， 所以，如果底边能最大 ， 就能找到最大面积

   所以，就可以采用尾指针从尾部遍历。

 

   如果它比3小，那么就要在0 - A.length - 2中找 ， 因为在这里面可能还存在面积更大的，而这个

   面积最大的临界情况就是第一个>=3！ 因为满足底最大! 那么接下来就不要比较A[1],A[2],A[3] 构成的大小，他们 一定比A[0]A[4]小！这样不就减少了没用的计算。直接进入A[1] = 7;

 

  同理，以A[1] = 7 为高 ， 查找第一个>=7的 , 但是，可能会想，已经过滤的尾部的元素

  不会与7构成一个更大的元素吗？比如，如果上面数组在5后面有一个2 ， 那么以A[0] = 3为边时，就已经

  被过滤掉了，不会在于其他元素比较了？为什么这能行了？

  可以这样考虑，它既然比3小，那么他就一定比7小(因为只有最小的那个元素在移动的啊)，对吧！所以，

  它与3为边时，底边还长1了，怎么可能与7再构成一个更大的面积！这又是在去除没用的计算。

  所以，7 就只要关心，看能否与当前尾指针所指的元素及其前面的元素构成一个更大面积！

  如此，一路遍历，直到头指针 >= 尾指针 

 

 

  总结：

  关键的地方就在于头尾指针的使用，我觉得他们的作用就是一种标志！

  标志，实际可能产生最大面积的范围

  以上只是个人的一些粗陋的理解.......

   

   代码：

 

public static int maxArea(int[] height) {
        int maxWater=0, left=0, right=height.length-1;
//头尾指针
        while(left<right) {
            maxWater = Math.max(maxWater,(right-left)*Math.min(height[left], height[right]));
            if(height[left]<height[right]) left++;
            else right--;
        }
        return maxWater;
    }