## Sunday, January 27, 2013

### [LeetCode] Container With Most Water, Solution

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

[Thoughts]
For any container, its volume depends on the shortest board.
Two-pointer scan. And always move with shorter board index.

[Code]
``````1:    int maxArea(vector<int> &height) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int start =0;
5:      int end = height.size()-1;
6:      int maxV = INT_MIN;
7:      while(start<end)
8:      {
9:        int contain = min(height[end], height[start]) * (end-start);
10:        maxV = max(maxV, contain);
11:        if(height[start]<= height[end])
12:        {
13:          start++;
14:        }
15:        else
16:        {
17:          end--;
18:        }
19:      }
20:      return maxV;
21:    }
``````