Container with most water
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
class Main {
public static void main(String[] args) {
/**
* https://leetcode.com/problems/container-with-most-water
*
* You are given an integer array height of length n.
* There are n vertical lines drawn such that the two endpoints of
* the ith line are (i, 0) and (i, height[i]).
*
* Find two lines that together with the x-axis form a container, such
* that the container contains the most water.
*
* Return the maximum amount of water a container can store.
*
* Notice that you may not slant the container.
*
* Input: height = [1,8,6,2,5,4,8,3,7]
* Output: 49
* Explanation: 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.
*/
int[] height = {1,8,6,2,5,4,8,3,7};
System.out.println(maxArea(height));
}
public static int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
// maxArea will keep the greatest area calculated and return it at the end
int maxArea = 0;
while (left < right) {
// We can capture the index of the lower area
int lowerHeightIndex = height[left] < height[right] ? left : right;
int lowerHeight = height[lowerHeightIndex];
// We can calculate the area with the lower element between height[left] and height[right] by
// the amount of heights in between the left and the right
int area = lowerHeight * (right - left);
if (maxArea < area) {
maxArea = area;
}
// We need to move the pointer from the lower height index according to the
// pointer referenced. For example: if the lower height came from the left pointer
// then we need to move the left pointer one position (left++). Otherwise, we need to move the
// right pointer one position (right--).
if (lowerHeightIndex == left) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
Java
INFO