# 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

two pointers方法需要确定

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

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

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

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

`area1 - area2 >= h1 - h2`

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