Difficulty: Medium#
Problem:#
Given an integer array height of length n. There are n vertical lines, 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 can be contained.
Note: You may not slant the container.
Analysis#
Can you "see" it at a glance?#
At first glance, this problem seems quite simple. Use two loops to calculate the amount of water and compare the maximum amount of water. 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 cause the processing to time out.
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 amount 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 height is moved, the height of the container does not change. The amount of water may even decrease. Moving the lower edge of the container is the only way to increase the amount of water. So, the plan is to loop once, move the smaller edge each time, compare the amount of water each time with the recorded maximum amount of water, and find the true maximum amount of water.
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" of the container, because it must have decreased, just continue moving. So I used two flags to record and improve the execution speed of the code.
So I did it
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 record the left and right sides
int maxHeightI = height[i];
int maxHeightJ = height[j];
//Record whether the left pointer (0) or the right pointer (1) was moved last time
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