Question

Formatted question description: https://leetcode.ca/all/11.html

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

@tag-array

Algorithm

The following is an example: [4,6,2,6,7,11,2] to explain.

1 . First, suppose we find the vertical line that can take the maximum volume as i, j (assuming i<j), then the maximum volume C = min( ai, aj) * (j- i);

2 . Below we look at such a property:

  • No line at the right end of j will be higher than it! Suppose there is k |( j<k && ak> aj), then ak> aj, so min(ai,aj, ak) =min(ai,aj), so the volume of the container formed by i, k C’= min(ai,aj) * (ki)> C, which is the most contradictory value with C, so there will be no line higher than it behind the proof j; To
  • Similarly, there will be no higher line on the left side of i; To What is this indicating? If we currently get the candidate: set x, y as two lines (x< y), then the two new edges that can be larger than it must be in the interval [x,y] And ax’> =ax, ay’>= ay;

3 . So we move closer from the two ends to the middle, and update the candidate values ​​at the same time; when shrinking the interval, first shrink from the smaller edge of x, y;

The intuitive explanation is: volume is area, which is affected by length and height. When the length decreases, the height must increase to increase the area, so we start to decrease from the longest length, and then look for a higher line to update Alternate

Code

Java

  • 
    public class Container_With_Most_Water {
    
    	public static void main(String[] args) {
    		Container_With_Most_Water out = new Container_With_Most_Water();
    		Solution2 s = out.new Solution2();
    
    		System.out.println(s.maxArea(new int[]{2,0,2}));
    	}
    
        // time: O(N)
        // space: O(1)
    	public class Solution {
    	    public int maxArea(int[] height) {
    	        int[] h = height;
    
    	        if(h == null || h.length == 0) {
    	            return 0;
    	        }
    
    	        int l = 0; // left
    	        int r = h.length - 1; // right
    
    	        int max = (r - l) * Math.min(h[l], h[r]); // possibly very first position is max area
    	        while(l < r) {
    	            if(h[l] < h[r]) {
    	                l++;
    	            } else {
    	                r--;
    	            }
    
    	            max = Math.max(max, (r - l) * Math.min(h[l], h[r]));
    	        }
    
    	        return max;
    	    }
    	}
    
    	// N^2. Time Limit Exceeded
    	public class Solution2 {
    		public int maxArea(int[] h) { // h: height
    			if (h == null || h.length == 0) {
    				return 0;
    			}
    
    			// possibly sanity check for negative int in array, throw something for debugging
    			// never trust the passed in parameter!
    
    			int i = 0;
    			int max = Integer.MIN_VALUE;
    			while (i < h.length) {
    
    				int j = i + 1;
    				while (j < h.length) {
    
    					max = Math.max(max, (j - i) * Math.min(h[i], h[j]));
    					j++;
    				}
    
    				i++;
    			}
    
    			return max;
    		}
    	}
    
    }
    
  • // OJ: https://leetcode.com/problems/container-with-most-water/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        int maxArea(vector<int>& A) {
            int N = A.size(), ans = 0;
            for (int i = 0; i < N; ++i) {
                if (!A[i]) continue;
                for (int j = i + 1 + ans / A[i]; j < N; ++j) {
                    ans = max(ans, min(A[i], A[j]) * (j - i));
                }
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = left = 0
        right = len(height) - 1
        while left < right:
          ans = max(ans, (right - left) * min(height[left], height[right]))
          if height[left] <= height[right]:
            left += 1
          else:
            right -= 1
        return ans
    
    

All Problems

All Solutions