LeetCode 011 盛最多水的容器

数组相关

问题

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

注意：你不能倾斜容器，n 至少是2。

解答

容器可容纳的水是受短边影响，所以最多就是短边高乘上宽（x坐标上距离）。
这边采用的是双指针法，一个从左到右，另一个从右到左。

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        int N = height.length;
        int l = 0, r = N-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;
    }
}

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$