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.

给定一个数组，从数组中找出两个数，构成一个容器，横坐标差是底。求容器盛水体积的最大值。

解题思路

动态规划

容器盛水的体积=底*两个数的最小值。

所以，每一次更新中，需要更新的只是最小值。

代码

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