[LeetCode] Container With Most Water, Solution

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.

» 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:    }