# 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

```java
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)

```java
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]);
    }
}
```