ContainerWithMostWater [source code]

public class ContainerWithMostWater {
static
/******************************************************************************/
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, max = -1;
        while (l < r) {
            max = Math.max (max, (r - l) * Math.min (height[l], height[r]));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return max;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ContainerWithMostWater.Solution tester = new ContainerWithMostWater.Solution();
    }
}

题目很有意思, 大概看懂了, 感觉一个sliding window, 不对, 没有counts信息, 谈不上sliding window; 当然, 这个题目用N^2是很好做的, 直接挑完算一下就行了; 有没有O(N)的方法?

对了, 这个题目在启发思路的时候其实还是动笔画了一下的: 给自己一点visualize的资料, 没坏处;

这题最好不要sort, 因为index有意义;

想不到O(N)的解法了, 随便写一个先过了好了;

不行, 直接的N^2的解法, 最后是TLE了. 先不着急想O(N)的解法, 有没有可能优化一下? 比如pruning?

加了优化到这里:

class Solution {  
    public int maxArea(int[] height) {  
        if (height.length <= 1)  
            return 0;  
        int max = 0;  
        for (int i = 0; i < height.length; i++) {  
            if (height[i] * (height.length - 1 - i) < max)  
                continue;  
            for (int j = i + 1; j < height.length; j++) {  
                int content = Math.min (height[i], height[j]) * (j - i);  
                if (content > max)  
                    max = content;  
            }  
        }  
        return max;  
    }  
}

还是TLE, 没办法了, 直接看答案了; 感觉还是小看这个题目了;

上面版本是照editorial写的, 速度是11ms (19%).

editorial

Approach #1 Brute Force [Time Limit Exceeded]

public class Solution {  
    public int maxArea(int[] height) {  
        int maxarea = 0;  
        for (int i = 0; i < height.length; i++)  
            for (int j = i + 1; j < height.length; j++)  
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));  
        return maxarea;  
    }  
}

Approach #2 (Two Pointer Approach) [Accepted]

Algorithm

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.

The algorithm can be better understood by looking at the example below:

1 8 6 2 5 4 8 3 7

How this approach works?

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.

For further clarification click here and for the proof click here.

public class Solution {  
    public int maxArea(int[] height) {  
        int maxarea = 0, l = 0, r = height.length - 1;  
        while (l < r) {  
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));  
            if (height[l] < height[r])  
                l++;  
            else  
                r--;  
        }  
        return maxarea;  
    }  
}

没想到Bloomberg居然也出这么难的题目了; 这个算法本身的代码也是看起来很简单, 但是背后的想法却不简单; 他上面给的这个解释, 只是一个很intuitive的解释, 并不完整;

明天白天看看discussion给的这些证明, 晚上自己先想一想. 不过算法证明, 尤其是这种就一个循环的证明, 要想到突破口是invariant.

晚上大概思考了一下, 感觉证明其实是不难的; 首先, 这题好像从invariant的角度并不那么好证明?

首先我发现, 这个算法其实就是一个greedy的算法, 一开始, 让width最大, 然后下面每一个iteration减少1的width, 同时move the wall that is less likely to reduce the area. 如果收缩longer这一边的, 那么area肯定降低, 但是如果收缩shorter这一边的, 至少有可能让area增加;

证明用什么思路? 我一开始用invariant感觉不好证明, 然后想着用greedy的方法证明, 但是发现我好像并不熟悉greedy算法的证明思路; 最后对这个算法的证明, 我的思路是这样的, 因为肯定有一个[a,b]的interval, 对应实际上的最大container; 在N^2的做法当中, 这个interval肯定会被iterate到; 而在这个O(N)的算法当中, 难点是证明能够iterate到这个interval: 因为我们是维护最大值, 只要你能iterate到这个interval, 那么最后返回的肯定就是他;

怎么证明能够iterate到? 用contradiction, 假如我们最后没有iterate到[a, b], 那么一定是在某一个包含[a,b]的区间的时候, 比如说是[a1, b1], a1 <= a, b1 >= b, 我们最后收缩的时候, 左右有一头夸过了a和b当中的一个;

一个问题首先澄清: 我们每一个iteration完成的动作是: shrink on the side of the shorter wall. 所以左右是无关的;

WLOG, 我们假设是b被b1超过了, 那么一定有一个iteration, 是a1 <= a, b1 == b, 并且我们马上要b1--. 这里有一个问题, b是[a,b]的longer还是shorter?

• 假如是longer, 那么在这个iteration, 我们决定了要--b1, 说明[a1] >= [b1], 但是我们又知道[b] >= [a], 这说明, 真正的最大interval应该是[a1, b], 这个跟一开始的假设是矛盾的; 注意, 如果你觉得这里这个等号有点麻烦, 可以把等号的情况分离出去单独处理;
• 假如b是shorter, 那么我们知道[a1] >= [b1], 那么最大interval应该是[a1, b], 因为反正最后的短板都是[b], 但是a1跟b的距离比a跟b的距离远, 这个也是跟一开始的假设矛盾;

这里可以看到, 基本就证明了;

这个解法貌似在2013年就被提出了:

@Shangrila said in Anyone who has a O(N) algorithm ?:

Here is a solution by n00tc0d3r from old discuss. Thanks n00tc0d3r.

    public int maxArea(int[] height) {    
       int len = height.length, low = 0, high = len -1 ;    
       int maxArea = 0;    
       while (low < high) {    
         maxArea = Math.max(maxArea, (high - low) * Math.min(height[low], height[high]));    
         if (height[low] < height[high]) {    
           low++;    
         } else {    
           high--;    
         }    
       }    
       return maxArea;    
     }

Here is the proof.
Proved by contradiction:

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.

这个证明的核心跟我的证明是类似的, 但是确实有点不太好理解;

当时还有人给出了一个很clean很理论学家风格的证明:

@wangjie said in Anyone who has a O(N) algorithm ?:

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].

刚开始看到这个证明以为是跟editorial的解释一样的, 不过后来想了一下, 我感觉他这个证明其实是很不错的; 在一个search algorithm里面, 如果我们能够证明每一个iteration的操作都是safe的, 那么就可以证明这个search最后是可以找到optimal的, 这个也是NLP的时候学到的一个观点;

这个是discussion最优的一个解释:

@kongweihan said in Yet another way to see what happens in the O(n) algorithm:

The O(n) solution with proof by contradiction doesn't look intuitive enough to me. Before moving on, read [the algorithm][1] first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where the row is the first line, and the column is the second line. For example, say n=6.

In the figures below, x means we don't need to compute the volume for that case: (1) On the diagonal, the two lines are overlapped; (2) The lower left triangle area of the matrix is symmetric to the upper right area.

We start by computing the volume at (1,6), denoted by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6  
1 x ------- o  
2 x x  
3 x x x   
4 x x x x  
5 x x x x x  
6 x x x x x x  

Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below (2,6) are eliminated.

  1 2 3 4 5 6  
1 x ------- o  
2 x x       o  
3 x x x     |  
4 x x x x   |  
5 x x x x x |  
6 x x x x x x  

And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6  
1 x ------- o  
2 x x - o o o  
3 x x x o | |  
4 x x x x | |  
5 x x x x x |  
6 x x x x x x  

Hope this helps. I feel more comfortable seeing things this way.

[1]: https://oj.leetcode.com/discuss/1074/anyone-who-has-a-o-n-algorithm

这个其实并没有证明任何东西, 只是告诉你发生了什么; 这个我不觉得很有什么启发意义;

底下有人提出这个算法跟一个其他题目的类似:

@benjamin19890721 said in Yet another way to see what happens in the O(n) algorithm:

I came up with this proof too, inspired by the step-wise linear search method in this blog: http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html. Glad that someone has shared the same idea.

一个解释:

@aiayumi said in Yet another way to see what happens in the O(n) algorithm:

Basically you are just trying to find the furthest taller edge the current one [i] can reach - a further but slightly taller edge, is better than a huge tall edge that is closer, since the max container is limited by each edge [i] itself - being the shorter edge. If [i] is the tallest, it can form no containers with its height.

Two-pointers solution, walking from each end, guarantees the shorter edge meets its furthest taller edge. Simple as that.

他的第一段倒是说的有理有据, 但是最后一句的这个guarantee是怎么得到的有点没头没脑?

Stefan给的解释:

@StefanPochmann said in Simple and fast C++/C with explanation:

Start by evaluating the widest container, using the first and the last line. All other possible containers are less wide, so to hold more water, they need to be higher. Thus, after evaluating that widest container, skip lines at both ends that don't support a higher height. Then evaluate that new container we arrived at. Repeat until there are no more possible containers left.

这个其实就是editorial给的那个说法, 并不严谨;

另外一个解释:

@mo10 said in Easy Concise Java O(N) Solution with Proof and Explanation:

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.

看起来很好, 但是他并没有证明why you can reach [a10, a21] in the first place.

Stefan后来又给了另外一个解释:

@StefanPochmann said in Simple and clear proof/explanation:

I've seen some "proofs" for the common O(n) solution, but I found them very confusing and lacking. Some even didn't explain anything but just used lots of variables and equations and were like "Tada! See?". I think mine makes more sense:

Idea / Proof:

1. 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.
2. All other containers are less wide and thus would need a higher water level in order to hold more water.
3. The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.

Implementation: (Python)

    class Solution:  
        def maxArea(self, height):  
            i, j = 0, len(height) - 1  
            water = 0  
            while i < j:  
                water = max(water, (j - i) * min(height[i], height[j]))  
                if height[i] < height[j]:  
                    i += 1  
                else:  
                    j -= 1  
            return 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.

这个解释稍微有条理一点, 但是感觉还是不够精准;

看了一圈感觉大部分的证明都一般般, 这个是我自己发的帖子:

@vegito2002 said in Proof with Pictures for O(N) algs: imperative rather than intuitive, easy to understand for all:

My proof seems long, but that's only because I want it to be as detailed as possible, it's not hard really.

Regarding the O(N) algorithm in the editorial solution, I browsed several discussion posts and personally find this:

@wangjie said in Anyone who has a O(N) algorithm ?:

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].

the proof that I like the most: in any searching heuristic, as long as you do safe pruning, you are guaranteed to find the optimal at last. I am not sure if this is an accurate enough formalism, but it works for me.

---

But I personally came up with a different approach of proof by contradiction: it does not depend on intuition so much, so presumably is easy to understand.

First, let's understand the algorithm:

public class Solution {  
    public int maxArea(int[] height) {  
        int maxarea = 0, l = 0, r = height.length - 1;  
        while (l < r) {  
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));  
            if (height[l] < height[r])  
                l++;  
            else  
                r--;  
        }  
        return maxarea;  
    }  
}

This is a greedy approach: we start with the maximum width, then shrink the width on the side with shorter wall. I want to make an obvious statement: whether the shunk side is on the left or right does not matter. This will help later proof.

First, think about the naive N^2 solution we all know, what do we do there? We try every height[i], height[j]. There got be an optimal height[a], height[b] that provides the maximum rectangle area.

During our new O(N) algorithm, if we know for sure that we will have one iteration that is at a, b (l == a, r == b), then we know for sure that we will return height[a], height[b] as the max interval: nothing can beat it. The tricky part is to prove, how do you know for sure that we will arrive at a, b during some iteration. This is actually what I try to seek in posts of proof.

Wait, we know for sure that a, b exists. If we never had a l == a, r == b iteration, then we must have missed it (the contradiction hypothesis). How could we miss it?

In the first iteration, we are at 0, N - 1, and we know that 0 <= a, b <= N - 1, that means, 0, N - 1 comprehends a, b we know for sure.

Now begins the hypothesis by contradiction:

If we missed it then there would be an iteration i, j where i, j does not overlap with a, b at all. Then i, j would go on converging:

Wait, too fast? How do we get here? Let's back up a little, there would be an iteration that we have to move one of i and j over one of a and b, like this:

Let's focus on the iteration where one wall of i, j coincides with one wall of a, b, remember, this must happen if we were to miss out a, b, because we move only one wall of i, j by one unit of width at each iteration.
Remember how we just said, left or right does not matter, so WLOG let's say b == j at this iteration, and we are about to do j-- right now. Remember that at this time, we have i, j comprehending a, b, which means i < a (i == a can't be included: you just reached a, b! which is against the contradiction hypothesis).

Now, the picture above shows that height[a] > height[b], this is not necessarily true, but let's enumerate:

• if height[a] >= height[b], and we will j-- now: that means height[i] >= height[j] == height[b], then the actual optimal interval should have been i, b rather than a, b: because i < a, so i, b has a larger width than a, b, with the shorter wall being height[b] in both cases. Thus we have a contradiction with the assumption of a, b being the optimal interval.
  
• if height[a] < height[b], and we are to j--: then again, we know height[i] >= height[b], and it's easy to see i, b has to be the actual optimal interval: it's wider, and it has a taller shorter wall. Again, contradiction.
  

End of Proof.

I hope this proof is easy enough to understand.

submission最优解:

class Solution {  
    public int maxArea(int[] height) {  
        if (height == null || height.length < 2)  
            return 0;  
        int volumn = 0, h, i = 0, j = height.length - 1;  
        while (i < j){  
            h = Math.min(height[i], height[j]);  
            volumn = Math.max(volumn, h * (j - i));  
            while (i < j && height[i] <= h) i++;  
            while (i < j && height[j] <= h) j--;  
        }  
        return volumn;  
    }  
}

基本就是加了一个base case, 然后循环改成了eager nested advance. 跳过所有不可能有改善的iteration, 这样其实跳过了很多的求max操作; 一个小的优化, 不过最后速度加成很多: 8(86).

Problem Description

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). 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.

Difficulty:Medium
Total Accepted:177.2K
Total Submissions:478.8K
Contributor:LeetCode
Companies
bloomberg
Related Topics
arraytwo pointers
Similar Questions
Trapping Rain Water