Problem
Given a size n array with non-negative integers a1, a2, ..., an. Each element ai at index i represents a vertical line from (i, 0) to (i, ai). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Solution
We can use 2 pointers to mark the two edges of the container. Pointer lo start at 0, hi at N-1. Then the 2 pointers move inward. The shorter side move one step. When lo and hi across, we finished the search. We have to search the entire array element, because one possible situation is, the max container is located near the middle, and it is very very tall.
public class MaxWater {
public static int max(int[] a) {
//1,8,6,2,5,4,8,3,7
// .
// .
int lo = 0;
int hi = a.length - 1; //8
int max = 0;
while(lo < hi) {//2,6
max = Math.max(max, Math.min(a[lo], a[hi]) * (hi - lo));//49
if(a[lo] < a[hi]) lo++;
else hi--;
}
return max;
}
public static void main(String...args) {
System.out.println(max(new int[]{1,8,6,2,5,4,8,3,7}));
}
}
public static int max(int[] a) {
//1,8,6,2,5,4,8,3,7
// .
// .
int lo = 0;
int hi = a.length - 1; //8
int max = 0;
while(lo < hi) {//2,6
max = Math.max(max, Math.min(a[lo], a[hi]) * (hi - lo));//49
if(a[lo] < a[hi]) lo++;
else hi--;
}
return max;
}
public static void main(String...args) {
System.out.println(max(new int[]{1,8,6,2,5,4,8,3,7}));
}
}
Time cost O(N), space cost O(1).
