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;
		}
	}

}

All Problems

All Solutions