[LeetCode] 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.

解法：

　　最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到指针重合为止就行了。

public class Solution {

    public int maxArea(int[] height) {

        int max = 0;

        int i = 0;

        int j = height.length - 1;

        while (i < j) {

            int lower = Math.min(height[i], height[j]);

            max = Math.max(lower * (j - i), max);

            if (height[i] < height[j]) i++;

            else j--;

        }

        return max;

    }

}

　　改进：如果较短的边向中间移动后，新的边比原来的短，可以直接跳过，找下一条边，减少一些计算量。

public class Solution {

    public int maxArea(int[] height) {

        int max = 0;

        int i = 0;

        int j = height.length - 1;

        while (i < j) {

            int lower = Math.min(height[i], height[j]);

            max = Math.max(lower * (j - i), max);

            if (height[i] < height[j])

                while (i < j && height[i] <= lower) i++;

            else

                while (i < j && height[j] <= lower) j--;

        }

        return max;

    }

}

巴特西

[LeetCode] 11. Container With Most Water ☆☆

最新文章

热门文章