« Back
in Leetcode Java Array Two Points read.

Leetcode 11 Container With Most Water.

Problem 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.


This problem seems familiar to the problem Trapping Rain Water.
But totally different ideas.

At first, I use the Exhaustive method to solve, the code is easy to implement, but it will show you runtime error.

public class Solution {
    public int maxArea(int[] height) {
        int maxwater=0;
        int water=0;
        for(int i=0;i < height.length;i++){
            for(int j=i+1;j < height.length;j++){
                water=Math.max(height[i],height[j])*(j-i);
                maxwater=Math.max(water,maxwater);
            }
        }
        return maxwater;
    }
}

So another way is similar to find the smallest sum. Use two pointer point to head the tail, and for this problem, we the factor determine the how much water we can hold is the shorter one. So we make it like this: we move the shorter one until we sweep the whole list.

public class Solution {
    public int maxArea(int[] height) {
        int maxwater=0;
        int water=0;
        int i=0;
        int j=height.length-1;
        int mark=0;
        while(i < j){
            if(height[i] < height[j]){
                water=height[i]*(j-i);
                i=i+1;
            }else{
                water=height[j]*(j-i);
                j=j-1;
            }
            maxwater=Math.max(water, maxwater);
        }
        return maxwater;
    }
}
comments powered by Disqus