每天一题LeetCode【第8天】

T11. Container With Most Water【Medium】

题目

给 n 个非负整数 a1,a2,...,an, 每个数代表了坐标（i,ai）。绘制 n 条两端为（i,ai）和（i,0）的竖线。找到两条线，和 x 组成一个容器，使得容器能够装下最多的水。

注意：不能倾斜容器，n 至少为2

思路

① 分析一下，这题是问能装多少水，而且不能把容器倾斜，所以要用公式：

公式： min(line1,line2)*|x2-x1|

② 下面代码的思路是从外向里收缩，因为讲道理的话从外向里两点本身就相距最远，容易一下就找到点（哈哈反正我是那么想的）

③ 是关键！因为从外往里，所以|x2-x1|一定不断减小，所以若要更大，就应该让min(line1,line2)改变，所以把line1,line2中偏小的那个往里缩才是有效操作（如果把大的那端往里缩min(line1,line2)只能变小，所以一定不行）

代码

代码取自 Top Solution，稍作注释

public class Solution {
    public int maxArea(int[] height) {
    //初始化 left 和 right 的值（right 是最右的数）
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
       // 套用公式，比较得到新的maxArea
        maxArea = Math.max(maxArea, Math.min(height[left], height[right])* (right - left));
        //短的那端往里缩，因为长的那端缩了一定比原来小
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return maxArea;
    }
}