Container With Most Water

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.

思路： 贪婪。从两段开始，计算面积。每次走一步，若左端高低较低，从左端走；反之，从右端走。

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

67. Container With Most Water