int maxArea(vector<int> &height) {
int l(0), r=height.size()1, result(0);
while(l < r){
if(height[l] < height[r]){
result = max(result, height[l] * (r  l));
int pivot = height[l++];
while(l < r && height[l] <= pivot) ++l;
}else{
result = max(result, height[r] * (r  l));
int pivot = height[r];
while(l < r && height[r] <= pivot) r;
}
}
return result;
}
A fast and easyunderstand cpp solution


python version:
def maxArea(self, height): """ :type height: List[int] :rtype: int """ l, r, result = 0, len(height)1, 0 while l < r: if height[l] < height[r]: result = max(result, (rl) * height[l]); pivot = height[l] l += 1 while l < r and height[l] <= pivot: l+=1 else: result = max(result, (rl) * height[r]); pivot = height[r] r = 1 while l < r and height[r] <= pivot: r=1 return result

As I see this algorithm has 3 parts.
1. Checking if there are more possiblities
Keeping the invariant of
l < r
means that left is on the left side of right. Ifl >= r
, it means that: the left is either the same as right (0width > 0area)
 or they're in the wrong order (negative area).
This is used in part 3 too.
2. Finding the max
if (height[l] < height[r]) { result = max(result, height[l] * (r  l)); } else { result = max(result, height[r] * (r  l)); }
which is the same as
result = max(result, min(height[l], height[r]) * (r  l));
Consider a container with two sides (
l
/r
): overflow._  \    \     lr
the area of the container is given by the smaller height (
r
) and their distance (r  l
). Cannot choose the other side (l
) because the water would just overflow. This is symmetric if we draw the column heights the opposite.3. Skipping the values that can't be better
if (height[l] < height[r]) { int pivot = height[l++]; while(l < r && height[l] <= pivot) ++l; } else { int pivot = height[r]; while(l < r && height[r] <= pivot) r; }
Removing the optimizations (postincrements) and the bounds checking (
l < r
, see part 1):if (height[l] < height[r]) { int pivot = height[l]; while (height[l] <= pivot) ++l; } else { int pivot = height[r]; while (height[r] <= pivot) r; }
it's easier to see that it's looking for the next element that is bigger than the pivot.
The two branches are just for choosing which side to start looking for a better possibility. The smaller side must be chosen, because the area is contained bymin(height[l], height[r])
(see part 2).Anything smaller than or equal to the pivot can be skipped because:
 the distance between current
l
andr
is getting smaller, so area getting smaller too  if a height is smaller than pivot the area is smaller too
If we find a bigger than pivot height we can hope for a bigger area (depending on how much taller it is).
The postincrement optimization is just there to not run an unnecessary loop of thewhile
for the pivot itself.