Wednesday, January 7, 2015

LeetCode 11: Container With Most Water

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.
public class Solution {
    public int maxArea(int[] height) {
        // The volume is (j-i) * min(ai, aj)
        // Left pointer traverse from left; Right pointer traverse from right
        int N = height.length;
        
        if (N <= 1)
            return 0;
            
        int left = 0, right = N-1;    
            
        int maxVol = (right-left)*Math.min(height[left], height[right]); // Max volume
        int curVol = 0; // Current volume
        
        while (left < right)
        {
            // Firstly move the line with min value
            if (height[left] < height[right])
                left++;
            else
                right--;
                
            curVol = (right-left)*Math.min(height[left], height[right]);
            
            if (curVol > maxVol)
                maxVol = curVol;
        }
        
        return maxVol;
    }
}

No comments:

Post a Comment