> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/two_pointers/container_with_most_water.md).

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/two_pointers/container_with_most_water.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.