We have to maximize the Area that can be formed between the vertical lines using the shorter line as length and the distance between the lines as the width of the rectangle forming the area.
The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.
We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Futher, we maintain a variable maxarea to store the maximum area obtained till now. At every step, we find out the area formed between them, update maxarea and move the pointer pointing to the shorter line towards the other end by one step.
Initially we consider the area constituting the exterior most lines. Now, to maximize the area, we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won't gain any increase in area, since it is limited by the shorter line. But moving the shorter line's pointer could turn out to be beneficial, as per the same argument, despite the reduction in the width. This is done since a relatively longer line obtained by moving the shorter line's pointer might overcome the reduction in area caused by the width reduction.
Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with a_ol and a_or (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. So, we must have visited one of them but not the other. WLOG, let's say we visited a_ol but not a_or. When a pointer stops at a_ol, it won't move until
The other pointer also points to a_ol. In this case, iteration ends. But the other pointer must have visited a_or on its way from right end to a_ol. Contradiction to our assumption that we didn't visit a_or.
The other pointer arrives at a value, say a_rr, that is greater than a_ol before it reaches a_or. In this case, we does move a_ol. But notice that the volume of a_ol and a_rr is already greater than a_ol and a_or (as it is wider and heigher), which means that a_ol and a_or is not the optimal solution -- Contradiction!
Both cases arrive at a contradiction.
Here is a simple proof for the solution. Use v[low, high] indicates the volume of container with low and high. suppose height[low] < height[high], then we move low to low+1, that means we ingored v[low, high-1],v[low, high-2],etc, if this is safe, then the algorithm is right, and it's obvious that v[low, high-1],high[low, high-2]...... can't be larger than v[low, high] since its width can't be larger than high-low, and its height is limited by height[low].
AKA, the general idea to find some max is to go through all cases where max value can possibly occur and keep updating the max value. The efficiency of the scan depends on the size of cases you plan to scan.
To increase efficiency, all we need to do is to find a smart way of scan to cut off the useless cases and meanwhile 100% guarantee the max value can be reached through the rest of cases.
In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.
Given a1,a2,a3.....an as input array. Lets assume a10 and a20 are the max area situation. We need to prove that a10 can be reached by left pointer and during the time left pointer stays at a10, a20 can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a10 and right pointer is at a21, the next move must be right pointer to a20.
Since we are always moving the pointer with the smaller value, i.e. if a10 > a21, we should move pointer at a21 to a20, as we hope. Why a10 >a21? Because if a21>a10, then area of a10 and a20 must be less than area of a10 and a21. Because the area of a10 and a21 is at least height[a10] * (21-10) while the area of a10 and a20 is at most height[a10] * (20-10). So there is a contradiction of assumption a10 and a20 has the max area. So, a10 must be greater than a21, then next move a21 has to be move to a20. The max cases must be reached.
publicintmaxArea(int[] height){
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
maxArea = Math.max(maxArea, Math.min(height[left], height[right])
* (right - left));
if (height[left] < height[right])
left++;
else
right--;
}
return maxArea;
}
The naive version would solve this in O(n2) time. It can be improved as follows to linear time:
Keep two indices i and j, that start on both ends of the array to process, height. Our final goal is to findi,j, such that
A(i,j)=(j−i)×min(height(i),height(j))
is maximized. At every step, if height[i] < height[j], move i up by one. Otherwise move j down by one, until the two pointers meet. We now show that this gives the maximal answer. Suppose we just computed A(i,j), and height[i] < height[j]. If we increase i by one, we will ignore all the values A(i,k) for i≤k<j. We now show that A(i,j)>A(i,k). Since height[i] < height[j], A(i,k) is bounded by the height[i] term, and since k<j, it follows that A(i,j)>A(i,k), and we can safely ignore all of the A(i,k) and move on to inspecting A(i+1,j). The case with height[i] > height[j] is symmetric.
publicintmaxArea(int[] height) {
int maxA = 0;
int i = 0;
int j = height.length-1;
while(i < j){
int curArea = (j-i) * (Math.min(height[i], height[j]));
maxA = Math.max(curArea,maxA);
if(height[i] < height[j]) i++;
else j--;
}
return maxA;
}
Initially we can assume the result is 0. Then we scan from both sides. If leftHeight < rightHeight, move right and find a value that is greater than leftHeight. Similarily, if leftHeight > rightHeight, move left and find a value that is greater than rightHeight. Additionally, keep tracking the max value.
publicint maxArea(int[] height){if(height ==null|| height.length<2){return0;}int max =0;int left =0;int right = height.length-1;while(left < right){
max =Math.max(max, (right - left)*Math.min(height[left], height[right]));if(height[left]< height[right])
left++;else
right--;}return max;}
The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
All other containers are less wide and thus would need a higher water level in order to hold more water.
The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.
defmaxArea(self, height):
i, j = 0, len(height) - 1
water = 0while i < j:
water = max(water, (j - i) * min(height[i], height[j]))
if height[i] < height[j]:
i += 1else:
j -= 1return water
Further explanation:
Variables i and j define the container under consideration. We initialize them to first and last line, meaning the widest container. Variable water will keep track of the highest amount of water we managed so far. We compute j - i, the width of the current container, and min(height[i], height[j]), the water level that this container can support. Multiply them to get how much water this container can hold, and update water accordingly. Next remove the smaller one of the two lines from consideration, as justified above in "Idea / Proof". Continue until there is nothing left to consider, then return the result.
Without loss of generality is a term used in proofs to indicate that an assumption is being made that does not introduce new restrictions to the problem. For example, in the proof of Schur's Inequality, one can assume that without loss of generality because the inequality is symmetric in , and . Without loss of generality is often abbreviated WLOG or WOLOG. Be sure not to write WLOG when you mean "with loss of generality"!
without loss of generality because the inequality is symmetric in 
, 
and 
. Without loss of generality is often abbreviated WLOG or WOLOG. Be sure not to write WLOG when you mean "with loss of generality"!