Container With Most Water

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.

C++:
01 class Solution {
02 public:
03     int maxArea(vector<int> &height) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         vector<int> A;
07         int left=0;
08         int right=height.size()1;
09         while(left<right)
10         {
11             int lh=height[left];
12             int rh=height[right];
13             int h=lh<rh?lh:rh;
14             A.push_back(h*(rightleft));
15             if(lh<rh)
16                 left++;
17             else
18                 right;
19         }
20         int result=0;
21         for(int i=0;i<A.size();i++)
22         {
23             if(A[i]>result)
24                 result=A[i];
25         }
26         return result;
27     }
28 };
Advertisements
This entry was posted in Array and linked list, Greedy algorithm. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s