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& height) {
        //naiv办法
        int len = height.size();
        if(len<2){  //至少要有两个以上的线方能组成容器
            return 0;
        }
        int maxArea=0;
        int minHeight = 0;
        for(int i=1; i=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& height) {
        int maxArea = 0;
        int len = height.size();
        int i=0, j=len-1;
        while(ib?a:b;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
};

二次刷题（2015-08-18）

class Solution {
public:
    int maxArea(vector& height) {
        int result = 0;
        
        int start = 0;
        int end = height.size() - 1;
        
        while(start
三次刷题2015-10-16
class Solution {
public:
    int maxArea(vector& 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]

 
转载请注明： » [LeetCode] Container With Most Water

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->