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 and n is at least 2.

Solution

(1) Java

At first I misunderstood the problem, the meaning of this problem is that any container formed by any two bars, even there has higher bar between these two bars, so code actually becomes more simpler:

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length-1;
        int rst = 0;
        while (left < right) {
            if (height[left] <= height[right]) {
                rst = Math.max(rst, height[left]*(right-left));
                left++;
            } else {
                rst = Math.max(rst, height[right]*(right-left));
                right--;    
            }
        }
        return rst;
    }
}

(2) Python

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        left, right = 0, len(height)-1
        rst = 0
        while left < right:
            if height[left] <= height[right]:
                rst = max(rst, height[left]*(right-left))
                left += 1
            else:
                rst = max(rst, height[right]*(right-left))
                right -= 1
        return rst

(3) Scala

object Solution {
    def maxArea(height: Array[Int]): Int = {
        if (height.length == 0) {
            return 0
        }
        var left: Int = 0
        var right: Int = height.length-1
        var rst: Int = 0
        while (left < right) {
            if (height(left) <= height(right)) {
                rst = Math.max(rst, height(left)*(right-left))
                left += 1
            } else {
                rst = Math.max(rst, height(right)*(right-left))
                right -= 1
            }
        }
        return rst
    }
}

11. Container With Most Water