The idea is keep two pointer, one from left, the other from right. For a given left number, find the first one from right that is no less than it. I try to make it O(n) by using two hashmap keep track of each number I come across.

But there is a problem when left is 2, and right is 200000, I need to put into map 199998 times.

```
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;
}
}
```