[Two Poitners] Container With Most Water

1. Example
Two Pointer , width need two index
s= [3,4,5,6,7,0,3]

|                 7
|              6  |
|           5 ~  |
|         4 ~    |
|      3   ~     |     3
|      |    ~     | 1
| __ |__~__ | ____


2. Implementation
Q1: for a ladder shape ?  X ,  Most Water ?
A1: calculate the area of that shape, the one with largest area contain most water X
Water can not be tilt, so inly calculate rectangular shape

Q1: any two vertical lines can form a ladder shape ? how to pair?
A1: nested for loop O(n^2) + area calculation. pair vertical line with any vertical line before it
e.g., line 3 ,line2 and  line3 ,line1 and line3 ,line0
X Q1: Under increasing array, more index, more area. If not increasing ?
X A1: stop at the not increasing one
X Q1: DP[i] = max(max)
Q1: largest height with largest width?
A1: maintain a width right-left, try to find the largest height.
Q1:  3 5
        0 4  =>4w*3 = 12
        4 5
        1 4  => 3w*4h= 12
        5 5
        2 4 = > 2w*5h = 10
left move to right if left is smaller , looking for larger height,even width just decrease 1
right move to left if right is smaller, looking for larger height, even width just decrease 1

// time:O(n), Space:O(1)
public int maxArea (int[] height)
{

      // validate the input
      if (height == null || height.length == 0)
           return 0;



     //int max = 0;
     //for ()
     //{
     //
     //}

      

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


     return max;

}

3. Similar Ones
(H) Trapping Rain Water
Maximum Rectangle
Maximum histogram