leetocde solution 11 Container　with Most Water
z
 2018-03-01 21:01:28  

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length -1;
        int maxArea = 0;
        while(left < right){
            maxArea = Math.max(maxArea, (right - left)*Math.min(height[left], height[right]));
            if(height[left]>height[right]){
                right --;
            }
            else
                left ++;
        }
        return maxArea;
    }
}
  • of couse we can go through all the possible solution to find the largest area. However that might be time comsumming. In order to improve the time compacity, we use a smart way to find the largest eara.
  • As you can see, the width of the container is an important factor as the eara is width * min(h1, h2) . we set the first height and the last height to be the start two lines. At every time, we move the lower lines to the next inner line as the width becomming shorter. In this way , we can filter out some lines which is not useful.