Difficulty: Medium#
Problem:#
Given an integer array height of length n. There are n vertical lines, where the two endpoints of the i-th line are (i, 0) and (i, height[i]).
Find two lines, which together with the x-axis forms a container, such that the container contains the most water.
Return the maximum amount of water that the container can hold.
Note: You may not slant the container.
Analysis#
Can you "see" it at a glance?#
At first glance, this problem seems very simple. Use two loops to calculate the water volume and compare the maximum water volume. There is no need to even keep track of when the water is at its maximum. "See it at a glance"
public int maxArea(int[] height) {
//Traversal
int max = height.length;
int maxarea = 0;
for (int n = 0; n < max; n++) {
for (int m = n; m < max; m++) {
int temp = (m - n) * Math.min(height[n],height[m]);
maxarea = Math.max(maxarea,temp);
}
}
return maxarea;
}
Result
Wow, this is not good. There are too many data points, and the two loops are causing a timeout.
Starting over#
The problem is caused by the two nested loops, so the goal is to reduce the number of loops to one or even fewer.
The hint suggests using two pointers. Starting from the left and right endpoints. If it is possible to move only one pointer in one direction at a time, then it can be done with only one loop. The volume of water is determined by the base of the container (the distance between the two pointers) and the height (the minimum value of the two pointers). The base of the container will only decrease as it moves towards the center. The height is the minimum value of the two pointers, so if the pointer for the higher side is moved, the height of the container will not change. The volume of water may even decrease. Only by moving the pointer for the lower side can the volume of water be increased.
So, the plan is to loop once, move the smaller side each time, compare the water volume each time with the recorded maximum water volume, and find the true maximum water volume.
public int maxArea(int[] height) {
//Two pointers
int max = height.length;
int i = 0;
int j = max - 1;
int maxarea = 0;
for (int n = 0; n < max; n++) {
maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return maxarea;
}
The result is
Further optimization#
I found that during the process of moving the left and right pointers towards the center. If the height of the pointer after the move is lower than before, then there is no need to calculate the "water volume" because it must have decreased, just continue moving. So I used two flags to record and improve the execution speed of the code.
So, here we go
public int maxArea(int[] height) {
//Optimized two pointers
int max = height.length;
int i = 0;
int j = max - 1;
int maxarea = 0;
//Two flags to indicate the two sides
int maxHeightI = height[i];
int maxHeightJ = height[j];
//Record whether the last move was made by the left pointer (0) or the right pointer (1)
int flag = 0;
for (int n = 0; n < max; n++) {
if (flag == 0) {
if (height[i] < maxHeightI) {
i++;
continue;
}else {
maxHeightI = height[i];
}
}
if (flag == 1) {
if (height[j] < maxHeightJ) {
j--;
continue;
}else {
maxHeightJ = height[j];
}
}
maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
if (height[i] < height[j]) {
i++;
flag = 0;
} else {
j--;
flag = 1;
}
}
return maxarea;
}
The result is indeed effective