Container With Most Water

int maxArea(vector<int> &height) {
    int res = 0;
    int l = 0, r = height.size()-1;
    while (l < r)
    {
        if (height[l] <= height[r])
        {
            res = max(res, (r-l) * height[l]);
            l++;
        }
        else
        {
            res = max(res, (r-l) * height[r]);
            r--;
        }
    }
    return res;
}

Here is the proof. Proved by contradiction:

Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with aol and aor (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. Sow when we have visited the one that shows up firstly, the program will laterly move from this one so that the program can never consider the pair(aol, aor).  WLOG, let's say we visited aol firstly but not aor. When a pointer stops at a_ol, it won't move until the right pointer arrives at a value, say arr, that is greater than aol before it reaches aor. In this case, we does move aol. But notice that the volume of aol and arr is already greater than aol and aor (as it is wider and same height), which means that aol and aor is not the optimal solution -- Contradiction!


Here is a simple proof for the solution. Use v[low, high] indicates the volume of container with low and high. suppose height[low] < height[high], then we move low to low+1, that means we ingored v[low, high-1],v[low, high-2],etc, if this is safe, then the algorithm is right, and it's obvious that v[low, high-1],high[low, high-2]...... can't be larger than v[low, high] since its width can't be larger than high-low, and its height is limited by height[low].