Showing posts with label Greedy. Show all posts
Showing posts with label Greedy. Show all posts

Wednesday, July 9, 2014

Leetcode - 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.
[Thoughts] Greedy算法, 从两头往中间靠
public class Solution {
    public int maxArea(int[] height) {
        int l=0;
        int r=height.length-1;
        int max = 0;
        int temp=0;
        while(l<r){
            temp = (r-l)*Math.min(height[r], height[l]);
            max = Math.max(temp, max);
            if(height[r]>height[l])
                l++;
            else
                r--;
        }
        return max;
    }
}