题目

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). nvertical 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.

Notice that you may not slant the container.

---

Example1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.

Example2

Input: height = [1,1]
Output: 1

Example3

Input: height = [4,3,2,1,4]
Output: 16

Example4

Input: height = [1,2,1]
Output: 2

题目大意

给出一个非负整数数组a1,a2,a3,……an,没个整数标识一个竖立在坐标轴x位置的一堵高度为ai的墙，选择两堵墙，和x轴构成的容器可以容纳最多的谁。

解题思路

方法一：暴力枚举

暴力枚举每一种可能性，然后比较。

代码

package leetcode;

public class D11_ContainerWithMostWater {

    public static int maxArea(int[] height) {
        int len = height.length;
        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int minNumber = Math.min(height[i],height[j]);
                if(maxArea < minNumber * (j - i)) {
                    maxArea = minNumber * (j - i);
                }
            }
        }
        return maxArea;
    }

}

复杂度分析

* 时间复杂度：O(N²),两层嵌套循环。
* 空间复杂度：O(1)。

方法二：双指针

这一题也是对撞指针的思路。首尾分别2个指针，每次移动以后都分别判断长宽的乘积是否最大。

代码

package leetcode;

public class D11_02ContainerWithMostWater {

    public static int maxArea(int[] height) {
        int i = 0, j = height.length - 1, maxArea = 0;
        while (i < j) {
            maxArea = height[i] > height[j] ?
                    Math.max(maxArea, (j - i) * height[j--]) :
                    Math.max(maxArea, (j - i) * height[i++]);
        }
        return maxArea;
    }

}

复杂度分析

* 时间复杂度：O(N),双指针遍历一次底边宽度N。
* 空间复杂度：O(1)指针使用常数额外空间。