【LeetCode】No.11. Container With Most Water -- Java Version

题目链接： https://leetcode.com/problems/container-with-most-water/

1. 题目介绍（容纳最多的水）

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

【Translate】： 给定一个长度为n的整数数组。将它们看成n条垂直线，其中，第i条直线的两个端点分别为(i, 0)和(i, height[i])。

Find two lines that together with the x-axis form a container, such that the container contains the most water.

【Translate】： 找出两条与x轴一起组成一个容器的线，这样容器就能容纳最多的水。

Return the maximum amount of water a container can store.

【Translate】： 返回容器所能储存的最大水量。

Notice that you may not slant the container.

【Translate】： 注意，容器不能倾斜。

测试用例：


约束：

2. 题解 2.1 简简单单小穷举 – O(n²)

  这一题其实很容易理解，就是求最大面积，底*高。感觉题目出的不符合现实生活，要算水的话应该求容积才对嘛，凑一个三维坐标。
  言归正传，穷举的思想就是遍历所有可能性，所以，我们就使用环中环即可，老一套，用res充当临时变量存储当前的结果，然后与max进行比较得到最大，最后返回即可。一气呵成，可惜超时。

    public int maxArea(int[] height) {
        int n = height.length;
        int res = 0;
        int max = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i+1; j < n; j++)
            {
                res = height[i] > height[j] ? height[j] * (j-i) : height[i] * (j-i);
                if(res > max)
                {
                    max = res;
                }
            }
        }
        return max;
    }

  然后我们来看一下官方Solution中的穷举解法，直接用max()函数，让代码显得更加干净整洁，不过还是难逃超时的命运。

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

​​

2.2 Two Pointer Approach – O(n)

  这种方法取了两个指针，一个在数组的开头，一个在数组的末尾，它们构成了数组的长度。此外，它们维护一个变量maxarea来存储到目前为止所获得的最大面积。在每一步中找出它们之间形成的区域，并更新maxarea，并将指针指向较短的线向另一端移动一步。

    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }

3. 可参考

[1] [Java] 2 Approaches: BF and Two Pointers with Image Explaination | Code Commented