LeetCode [11] Container With Most Water

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 and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Note: always skip the shorter line because we can't compose a larger container with narrower space.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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