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.
» 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: }
No comments:
Post a Comment