康瑞部落

Container With Most Water

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.

解题思路：

这道题的意思是直角平面上有n条垂直于x轴的线，相邻的线相距1，选取两根线，与x轴构成一容器。求这样的容器能最多够装多少水？

1、基本方法，两两组合，计算出最大值。时间复杂度为O（n^2）。产生超时错误。

class Solution {
public:
    int maxArea(vector<int>& height) {
        //naiv办法
        int len = height.size();
        if(len<2){  //至少要有两个以上的线方能组成容器
            return 0;
        }
        int maxArea=0;
        int minHeight = 0;
        for(int i=1; i<len; i++){
            minHeight = height[i];
            for(int j=i-1; j>=0; j--){
                minHeight = min(height[i], minHeight);
                if(minHeight==0){
                    break;
                }
                maxArea=max(maxArea, minHeight*(i-j));
            }
        }
        return maxArea;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
    
    int max(int a, int b){
        return a>b?a:b;
    }
};

2、比较talent的办法，两边夹，若左边木板小于右边，移动左边木板，否则移动右边木板。因为只有这样容量才有可能变大。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int len = height.size();
        int i=0, j=len-1;
        while(i<j){
            maxArea=max(maxArea, min(height[i], height[j])*(j-i));
            if(height[i]<height[j]){
                i++;
            }else{
                j--;
            }
        }
        
        return maxArea;
    }
    
    int max(int a, int b){
        return a>b?a:b;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
};

二次刷题（2015-08-18）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int result = 0;
        
        int start = 0;
        int end = height.size() - 1;
        
        while(start<end){
            result = max(result, (end - start) * min(height[start], height[end]));
            if(height[start] < height[end]){
                start++;
            }else{
                end--;
            }
        }
        
        return result;
    }
};

三次刷题2015-10-16

class Solution {
public:
    int maxArea(vector<int>& height) {
        int result = 0;
        int len = height.size();
        int start = 0, end = len - 1;
        while(start < end){
            result = max(result, (end - start) * min(height[start], height[end]));
            if(height[start]<height[end]){
                start++;
            }else{
                end--;
            }
        }
        return result;
    }
};