Container with most water @ leetcode

微博：http://www.weibo.com/cathyhwzn

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

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.

First of all, to understand the problem. What it asks is, to find the maximun value of (i-j)*min(a_i, a_j). At the first , I only think of brute force solution which will cost O(n^2). Then I found a solution with linear cost. Set two pointers, point to begin and end. Move the pointer which points to the smaller element in array. The algorithm is simple, the hardest part is to prove the correctness of this algorithm. 

Because the contain volume is decided by the shorter line between two.
Since i is lower than j,  so there will be no jj < j that make the area from i,jj is greater than area from i,jso the maximum area that can benefit from i is already recorded.thus, we move i forward.