2.8 Container With Most Water

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.

Method

for a container we only need to consider the short plank. the widest container is 0 - (len - 1) when we go to the inner container, its width will decrease so if we want to contain more water we need higher plank. so we only need to compare the plank with the low one

Time and Space Complexity

o(n)

Code

public class Solution {

   public int maxArea(int[] height) {
      if (height == null || height.length <= 1){
          return 0;
      }
      int len = height.length;

      int left = 0;
      int right = len - 1;


      int low = Math.min(height[left], height[right]);
      int max = (right - left) * low;

      while (left < right){
            while (left < right && height[left] <= low){
                  left++;
            }

            while (left < right && height[right] <= low){
                  right--;
            }
            low = Math.min(height[right], height[left]);
            //System.out.println(low);
            max = Math.max(max, (right - left) * low);
      }
      return max;
}

}