盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。1

问题分析

1、实例抽象化
由题目的描述，可以将问题表述如下：
a.面积表示：areaN=min(ai,aj)*|i-j|，则面积最大可表示为max(areaN)；
对于最大值，我们一般会考虑动态规划，贪婪法，无则用穷举法。
而贪婪法的核心思想则是为了降低穷举法的重复不必要操作。本题中面积的个数是有限的，为n!个面积，为此可以运用穷举法得到结果。同时，问题就转换成求n(n+1)/2个数中，最大的数是多少。那么怎么求解这个最大值呢？？？可以一个一个比较，那么加上排列组合的情况，时间复杂度为O(n(n+1)/2)。再分析，既然是求最大值，可不可以联想到分治，贪婪的思想呢，将时间复杂度降到O(n)呢？答案是可以的，我们可以这么想，一个数组中的最大数势必大于其它所有的数，即其它所有的数都会小于最大的数，为此可以得出：
a.以x轴为索引,即i，以height[i]表示所在索引的高,分别从两端搜索,表示为left=0,right=i;
b.那么可以得到如下结论：
1.当前left,right的面积为(表示为cur_area)：(left-right)*min(height[left],height[right]),left移动方向为+,right移动方向为负;
2.运用贪婪思想，可以对left或right进行转移。那么怎么转移呢？
1)首先left和right的转移粒度为1,因此，只要height[left]>height[right]，则当前left中的最大值只可能在(left,right–)空间上，反之亦然。
2)总的思路就是不断找当前索引的最大值。

第一种思路的代码实现（js）

var maxArea = function(height) {
    var max_area=0;
    for(var i=0;i<height.length;i++){
        for(var j=i;j<height.length;j++){
            
            var cur_area=height[i]<height[j]?height[i]*Math.abs(i-j):height[j]*Math.abs(i-j);
            if(cur_area>max_area){
                max_area=cur_area;
            }
        }
    }

    return max_area;
};

第二种思路的代码实现（js）

var maxArea = function(height) {
    var max_area=0;
   	var left=0;
   	var right=height.length-1;
	while(left<right){
		var w=height[right]-height[left];
		var h=0;
		if(height[left]<height[right]){
			h=height[left];
			left++;
		}else{
 			h=height[right];
 			right--;
 		}
	    var cur_area=w*h;
	    if(max_area<cur_area){
			max_area=cur_area;
		}
	}
    return max_area;
};

总结

虽然这道题分析起来简单，但如何有逻辑性的去分析问题才是关键所在，充分利用具体的条件不断降低算法的时间复杂度，无论是在工作中，还是做题，都必须要把握的。学算法主要学的是分析问题的思路，具体怎么分析？怎么去证明自己的分析？这也是在培养自己理性思考问题的一个过程。