5/30/2014

45. Container with most water

public class Solution {
    public int maxArea(int[] height) {
        if (height.length<2) return 0;
       
        int res = 0;
        int i = 0;
        int j = height.length-1;
        int lasti = 0;
        int lastj = 0;
        int localmax = 0;
       
        while (i<j) {
            if (height[i]<height[j]) {
                localmax = (j-i)*height[i];
                if (res<localmax) res = localmax;
                lasti = height[i];
                while (i<j && lasti>=height[i]) {
                    i++;
                }
            } else {
                localmax = (j-i)*height[j];
                if (res<localmax) res = localmax;
                lastj = height[j];
                while (i<j && lastj>=height[j]) {
                    j--;
                }
            }
        }
       
        return res;
    }
}

1 条评论:

  1. 1. two pointers, i=0, j=len-1.
    2. calculate area: s=(j-i)*min(height[i], height[j]);
    3. update lasti or lastj.

    回复删除