[LeetCode] Container with Most Water

Problem Statement (link):

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.

Analysis:
The naive O(n^2) brute force is apparently not optimal.

An O(n) algorithm goes like this:
- Start from the very beginning and end of the vector, we calculate the volume hold by these two boards;
- Compare the height of current boards, advance the shorter board;

To justify this algorithm, think about the following case:
Suppose we are currently at left index i, right index j. If height i is smaller height j, then with any other height jj (i<jj<j), the area(i, jj) < area(i, j). The reason is that the container area is determined by the shorter height of the two boards, i.e., board i. In other words, the maximum area that determined by board i is already found.

Code:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int left=0, right=height.size()-1;
        int vol=min(height[left], height[right]) * (right-left);
        while (left<right) {
            if (height[left]<height[right]) left++;
            else right--;
            vol=max(vol, min(height[left], height[right]) * (right-left));
        }
        return vol;
    }
};