11.盛最多水的容器

11. 盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/)

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/container-with-most-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：
1
2
输入：[1,8,6,2,5,4,8,3,7]
输出：49

解题思路

面积为宽 * 高。宽为数组下标的差值，高为数组中两个元素较小的元素。假设i,j分别为i，j可盛水的面积，则得出以下公式

1

int area = Math.min(nums[i],nums[j]) * (j - i);

一，暴力法

暴力法是遍历每一种可能性，思路很容易理解，代码也非常易懂.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// 暴力法
    public int maxArea1(int[] height) {
        int len = height.length;
        int ans = 0;
		
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {

                int area = Math.min(height[i], height[j]) * (j - i);
                ans = Math.max(ans, area);
            }
        }

        return ans;
    }

时间复杂度 : O(N ^ 2)

空间复杂度 : O(1)

毫无疑问，执行时间很长，如图

二，双指针

接下来，我们使用一种时间复杂度为 O(N) 解决这个问题。

思路：面积和宽度高度有关系，分别从数组的宽度最大到宽度为1的最大面积，取出计算出的最大值即可。

做法：使用两个指针i,j分别指向数组头部和尾部(j - i为宽)，i，j处较小者为高,计算出面积。当nums[i] > nums[j] 时, j–, 再次计算面积，当nums[i] < nums[j] 时，i++;

代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


    public int maxArea2(int[] nums) {
        int len = nums.length;
        int max = 0,i = 0, j = len - 1;
        while (i < j){
            int area = Math.min(nums[i],nums[j]) * (j - 1);
            max = Math.max(area,max);

            if (nums[i] > nums[j]){
                j --;
            }else{
                i ++;
            }
        }
        return max;
    }

时间复杂度： O（N）

空间复杂度： O（1）

Contents

11. 盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/)

解题思路

一，暴力法

二，双指针