Container with Most Water

Question

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.

Notice

You may not slant the container.

Example

Given [1,3,2], the max area of the container is 2.

Tags

Two Pointers Array

Related Problems

Medium Trapping Rain Water

Analysis

求灌水最多的两个柱子组合，与Trapping Rain Water有一些类似。联想到使用Two Pointers的方法。

two pointers方法需要确定 1. 何时两个pointers终止移动跳出循环，能够包含所有情况。这里仍然是left&right pointers相遇。 2. 何时移动左右pointers。灌水多少不仅与两个柱子的高度有关，也与两个柱子的距离有关。如何使得存放的水更多呢？较短的那一个柱子决定了灌水的area，因此可以移动指向较短的柱子的pointer，对于相会的pointer，一般趋势均为向中间移动，因此如果 heights[left] < heights[right]，则left++，反之right--。

比如，对于如下一个数组heights[]：

[1, 3, 1, 2, 4, 2]

应该如何移动pointers？

1 3 1 2 4 2
-----------
        |
  |     |
  |   | | |
| | | | | |
-----------
0 1 2 3 4 5

初始情况下，left = 0, right = 5, heights[0] = 1, heights[5] = 2，也就是 area = 5 * 1 = 5； 因为heights[left] < heights[right]，因此left++, left = 1，更新后area = 4 * 2 = 8； 这时，heights[left] > heigths[right]，于是right--, right = 4, 更新后area = 3 * 3 = 9； 依次类推，当left，right相遇时，循环结束，得到最大area为9.

问题：为何较短的pointer向中间移动？

可以假设两个柱子距离为n, 较短的柱子高度为h，那么中间可以存放水的area为n * h。 假设初始状态下heights[left] < heights[right]。

如果令left++，此时柱子距离为n - 1，同时较短柱子为h1，那么area1 = (n - 1) * h1； 如果令right--，此时柱子距离n - 1，同时较短柱子为h2，那么area2 = (n - 1) * h2；

两个方向得到的面积之差：

area1 - area2 = (n - 1) * h1 - (n - 1) * h2 = (n - 1) * (h1 - h2)

假定 n - 1 >= 1，（n - 1 < 0 说明heights[]为空，n - 1 < 1说明 n = 1，则仅有一种area，不必讨论）

做一下不等式变换

area1 - area2 >= h1 - h2

因为heights[left] < heights[right]的设定，（并只考虑left/right中间的柱子高于两侧的情况，因为如果低于heights[left], heights[right]将无法得到更大的水面积）如果right--，水位的最高高度将小于left++时，水位的最高高度。

Solution

Two Pointers

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    public int maxArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;

        int left = 0;
        int right = heights.length - 1;

        int area = 0;

        while (left < right) {
            if (heights[left] < heights[right]) {
                area = heights[left] * (right - left);
                max = Math.max(area, max);
                left++;
            } else {
                area = heights[right] * (right - left);
                max = Math.max(area, max);
                right--;
            }
        }
        return max;
    }
}

Two Pointers (Updated)

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    public int maxArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;

        int left = 0;
        int right = heights.length - 1;

        int area = 0;

        while (left < right) {
            area = calculateArea(left, right, heights);

            if (heights[left] < heights[right]) {
                max = Math.max(max, area);
                left++;
            } else {
                max = Math.max(max, area);
                right--;
            }
        }
        return max;
    }

    /**
     * Calculate area based on left, right pointers
     *
     * @param {int} left
     * @param {int} right
     * @param {int[]} heights
     * @return {int} an integer
     */
    public int calculateArea(int left, int right, int[] heights) {
        return (right - left) * Math.min(heights[left], heights[right]);
    }
}