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

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

如果你看不懂英文，我给你提供了中文版的链接：https://leetcode-cn.com/problems/container-with-most-water/ 还有，点击阅读原文可以进入leetcode原题

示例

Input: [1,8,6,2,5,4,8,3,7]
Output: 4

难度系数

Medium

解答

这个其实就相当于算坐标之间所围成的面积，一种比较简单的方法就是算出所有坐标的组合，然后看看哪两个围成的面积比较大，时间复杂度是O(n2)。代码如下：

    public int maxArea(int[] height) {
        int max = 0;

        for (int i = 0; i < height.length; i++) {
            int temp = 0;
            for (int j = i + 1; j < height.length; j++) {
                // 算出所围成的面积
                max = Math.max(max,(j-i)*Math.min(height[i], height[j]));
            }
        }
        return max;
    }

不知道大家有没做过之前的两数之和所用到的双指针法，就是用两个指针从数组的左右两边往中间遍历，其实我们这道题就可以采用这种方法了。其思想是：用两个指针 left 和 right 分别指向数组的最左边和最右边，如果arr[left] > arr[right]，则让右边的指针向左移动，否则，让左边的指针向右移动。

每次移动都会计算出此时围成的面积，并且用一个变量来记录最大的面积。直接看代码吧：

    //双指针的模式做
    public int maxArea2(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (right > left) {
            max = Math.max(max,(right-left)*Math.min(height[right], height[left]));
            if(height[right]>height[left])
                left++;
            else
                right--;
        }
        return max;
    }

这个方式的时间复杂度是 O(n)。这种双指针法在很多地方都有用到，大家可以多试着去使用。