11. Container With Most Water - jiejackyzhang/leetcode-note GitHub Wiki

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.

Array类题目

container面积为min(ai, aj)*(j-i)，若使用brute force，则时间复杂度为O(n^2)。

注意到container的面积受限于较短的height，宽度则是越大越好。 因此若我们设置两个指针从Array两端开始计算，移动较高height那一端情况不会更优，而移动较低height的那一端则可能带来更优的情形。 终止条件为两指针相遇，因此时间复杂度为O(n)。

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