Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Naive Way: I try to draw an example like [1 2 1 3 2 1 2 1]. It turns out that for a given number h[i], whether the next position is great than h[i] or no greater than h[i] won't determine the largest capacity using h[i]. Only the last h[j] >= h[i] matters. So I tried two pointers, one from left and one from right, using two hashmap to keep track of number->position pairs.

Below code is based on that idea.

 public class Solution {  
   public int maxArea(int[] height) {  
     Map<Integer, Integer> rightMost = new HashMap<Integer,Integer>();  
     Map<Integer, Integer> leftMost = new HashMap<Integer, Integer>();  
     int left = 0, right = height.length-1;  
     int max = 0;  
     while(left < right){  
       while(left < right && leftMost.containsKey(height[left])) left++;  
       leftMost.put(height[left],left);  
       if(rightMost.containsKey(height[left])) max = Math.max(max,(right-left)*height[left]);  
       else{  
         while(left < right && height[right] < height[left]){  
           max = Math.max(max,(right-left)*height[right]);  
           rightMost.put(height[right], right);  
           right--;  
         }  
         for(int i = height[left];i <= height[right];i++)  
           rightMost.put(i,right);  
         max = Math.max(max,(right-left)*height[left]);  
       }  
     }  
     return max;  
   }  
 }  

This code has a big shortcoming in that it is not exact O(n), if two numbers are far away, say 2 and 200000, need to put into the map 200000 times. It is definitely not an ideal solution.

Improved Way: I finally realize that when a number as large as 200000 was met on the right, it matches almost all the left numbers. Right pointer don't need to move any more, Which means only the minimum of left and right should move! And integrate with the idea that only left and right boundaries matter. I finally come up with this code. Real O(n).

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