首页 > 代码库 > Container With Most Water

Container With Most Water

-----QUESTION-----

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.

-----SOLUTION-----
class Solution {
public:
    int maxArea(vector<int> &height) {
        if(height.size() ==1) return 0;
        int width;
        int tall;
        result = 0;
        int i = 0;
        int j = height.size()-1;
        while(i<j)
        {
            tall = min(height[i],height[j]);
            width = j-i;
            if(tall*width > result) result = tall*width;
            if(height[i] > height[j]) j--;
            else i++; 
        }
        return result;
        
    }
private:
    int result;
};
以下算法在judge large时time limit exceeded
class Solution {
public:
    int maxArea(vector<int> &height) {
        if(height.size() ==1) return 0;
        int width;
        int tall;
        result = 0;
        for(int i = 1; i< height.size(); i++)
        {
            for(int j = i+1; j<height.size(); j++)
            {
                tall = min(height[i],height[j]);
                width = j-i;
                if(tall*width > result) result = tall*width;
            }
        }
        return result;
    }
private:
    int result;
};


Container With Most Water