11、盛最多水的容器-Leetcode（java）_盛水最多的容器java

1、题目要求

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量（注意：不能倾斜容器）

测试用例如下：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

2、个人愚笨的思路

    /**
     * 使用双重for循环遍历
     */
    public static int maxArea(int[] height) {
        //定义一个变量，存放最多的水
        int area = 0;

        //遍历,获取两条垂线
        for (int i = 0; i < height.length-1; i++) {
            for (int j = i+1; j < height.length; j++) {
                area = Math.max(area,(j - i) * (Math.min(height[i], height[j])));
            }
        }
        System.out.println("最大的水容量为:"+area);
        return area;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结果如自己所想，虽然使用测试用例能得到想要的结果，提交后却告知超出时间限制。

3、官方推荐思路

使用双指针。
解析题意，可知 容纳的出水量=两个指针中指向的数字中的较小值*指针之间的距离。

双指针代表了什么？
双指针代表的是可以作为容器边界的所有位置的范围。在最开始，双指针left和right分别指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界。（留一个问题：为什么要移动指针对应数值偏小的指针？）

时间复杂度：O(N)，双指针总计最多遍历整个数组一次。
空间复杂度：O(1)，只需要额外的常数级别的空间。

    public static int maxAreaSecond(int[] height) {
        //使用双指针，即左右两边同时移动
        int left = 0;
        int right = height.length-1;
        int area = 0;
        int result = 0;

        while (left < right){
            //获取面积
            area = (right-left)*(Math.min(height[right],height[left]));
            result = Math.max(area,result);
            //然后谁的值小就移动谁
            if (height[left]<= height[right]){
                left++;
            }else {
                right--;
            }
        }
        System.out.println("使用双指针："+result);
       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

针对官方的解释，做出如上优化代码，成功执行。

时间从9ms到4ms，去掉了注释和打印语句（原来是打印语句耗时）

4、大神思路

//参照大神思路，修改自己的代码!
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int result = 0;

        while (left < right){
            int minHeight = Math.min(height[right], height[left]);
            int area = (right-left)*minHeight;
            result = Math.max(area,result);
            while (height[left]<= minHeight && left<right){
                left++;
            }
            while (height[right]<= minHeight && left<right){
                right--;
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19