LeetCode[11] - 盛最多水的容器

题目

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

题目

分析

这道题本身并不是很难（其实我跳过了一题，第十题，实在是有点智商不够）

• 解法1：暴力算法
  两层for循环从头算到尾，提交后击败了0.00%的玩家····这个我就不多讨论了···

• 解法2：分析一下矩形面积与长和宽相关，我们不妨让宽为最大，即取数组两端(a[0],a[lenght-1])，那么高即为min(a[0],a[lenght-1]),那么我们下组长宽如何去选取呢？其实很简单，我们将某一端向内移动一位，那么是哪一端呢？当然是选择短的一端移动才有可能得到大的，即：
  如果 a[0]>a[length-1]=>a[0],a[length-2];
  否则 a[0]<a[length-1]=>a[1],a[length-1];
  思路清晰了就可以coding了。

    public int maxArea(int[] height) {
        int res=0;
        int l=0;
        int r=height.length-1;
        while(l!=r){
            res=Math.max(res,Math.min(height[l],height[r])*(r-l));
            if(height[l]>height[r]){
                r--;
            }else{
                l++;
            }
        }
        return res;
    }

提交一下，测试用例耗时由几百毫秒降至8毫秒~~