力扣热门100题——盛水最多的容器（暴力解法，双指针，贪心）_盛水最多容器

4、盛水最多的容器

1.问题描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

2.示例

示例 1：

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

输入：height = [1,1]
输出：1

3.提示

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

4.具体解法（暴力解法，双指针，贪心）

//方法一：暴力解法
//第一反应是，找两个最长的板子，那之间的水不就是最多，但示例的例子就可以提醒自己，这么想是不对的
//那么就想到暴力遍历的方式
//因为两块板子之间的盛水量，就是两块板子的距离乘上低板子的高度
//所以弄上一个双层for循环，做i和j的差值（不用再多减一，九个线，数组下标最大值正好是8,8-0正好是最大的距离8）
//差值乘height[i]和height[j]中的小者，存储到一个最大值变量中，最后返回即可。
//附上自己写的暴力循环，超出时间限制
//发现很多超出时间限制的，问题就在于，二层循环有很多冗余的操作，一般都是从这里入手去解决相关的问题
//自己应该去找到一个解决的思路，其实之前已经有了，只不过自己没去细致的掌握，应该掌握一下，可以做到一通百通，起码在暴力这一块，可以做到能用就能通过
/*
class Solution {
    public int maxArea(int[] height) {
        int maxsum=0;//最后返回的最大值
        int nowsum=0;//临时的最大值
        int len=height.length;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(height[i]<height[j]){
                    nowsum=height[i]*(j-i);
                }
                else{
                    nowsum=height[j]*(j-i);
                }
                if(nowsum>maxsum){
                    maxsum=nowsum;//这里我想直接在那个答题界面用max方法，但是会报错，应该还是得导包才可以用
                                  //好像是因为我没有用类名直接调用，我直接写的方法名，少写了类名
                }
            }
        }
        return maxsum;

    }
}
 */

//暴力解法的改进
//解决办法就是对height[i]进行一个判断，只有大的才有机会留下，小的不可能容量更大了，所以直接都不判断了
/*
class Solution {
    public int maxArea(int[] height) {
        if(height.length==1||height.length==0){
            return 0;
        }
        int max=0;
        for(int i=1;i<height.length;i++){
            if(height[i]>max/i)//注释掉这一句就会最后超时
                               //然后我把这一句给改成加个{}将后面的for包裹起来，也可以不超时
                               //我这样改的意义其实就是，如果这个height[i]比上一个更小，那肯定最大值还没有前面的那个做边的时候更大，直接跳过
            for(int j=0;j<i;j++){
                if(i==j)
                    continue;
                max=Math.max(max,(i-j)*Math.min(height[j],height[i]));
            }
        }
        return max;
    }
}

 */


//方法二：双指针
//这个思路我隐约也有感觉了，但是并没有完整的想出来
//他的核心思路就是两个指针从两端，计算盛水量，然后小的指针向中间移动一位，再计算盛水量，并更新最大值，以此类推
//这个原理可行的依据在于：双指针代表的是 可以作为容器边界的所有位置的范围。
//在一开始，双指针指向数组的左右边界，表示 数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。
//在这之后，我们每次将 对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。
//而为什么数字较小的那个指针不可能再作为容器的边界了？
//因为我们假设左右指针的高度是x和y，之间的距离是t，（x<y），那么容量应该是x*t，如果是右指针移动，那么无论怎样，容量都不会大于这个x*t了
//因为t会变小，而短板效应决定容器的高度最大也就是x了，所以一定不会变大了
//所以说，这个左指针作为边界的最大值我们已经找到了，而且后面不需要再用它作为边界了，那么自然就应该可以舍弃他了
//而且舍弃之后，就相当于回到最一开始指向左右边界一样，是一个新的左右边界，所以可以继续像前面一样考虑问题
/*
public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;//定义左右指针
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
}
 */
//同样的双指针思路，下面的这个击败百分之98,2ms
//而上面官方的双指针，击败百分之12,5ms
/*
class Solution {
    public int maxArea(int[] height) {
        int len=height.length;
        //i,j ： 将指针指向数组两侧
        int i=0;
        int j=len-1;
        //res 计算出此时的储水量
        int res=Math.min(height[i],height[j])*(j-i);
        //给出扫描停止条件：i=j
        while(i<j){
            //找出较小的高度，将对应指针向内侧移动，直到找出大于原来高度的
            if(height[i]<=height[j]){
                int temp=i;
                while(height[i]<=height[temp] && i<j){
                    i++;

                }
                res=Math.max(res,Math.min(height[i],height[j])*(j-i));
            }else{
                int temp=j;
                while(height[j]<=height[temp] && i<j){
                    j--;
                }
                res=Math.max(res,Math.min(height[i],height[j])*(j-i));
            }

        }
        return res;
    }
}
 */

//下面这个我没运行，但是代码真的太简洁了
//也是双指针，用这个三目运算符，整个代码简洁明了
/*
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ?
                    Math.max(res, (j - i) * height[i++]):
                    Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }
}
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

5.收获

• 发现很多超出时间限制的，问题就在于，二层循环有很多冗余的操作，一般都是从这里入手去解决相关的问题，自己应该去找到一个解决的思路，其实之前已经有了，只不过自己没去细致的掌握，应该掌握一下，可以做到一通百通，起码在暴力这一块，可以做到能用就能通过。自己试着去想了一下找二层循环的冗余部分，发现不是很容易就能想到呢
• 双指针的思路好像也是经常使用的，可以避免一些重复的操作
• max方法的调用时类名直接调用，静态类嘛。Math.max（a，b）即可
• 即使是同样的算法，还能有不小的差别，其中的原因还是没有掌握，但是应该是跟底层的逻辑结构有关系
• 对于双指针的解法，有贪心的说法，就是每一次都是把短的舍弃，这种贪心的做法，只有移动短的，才可能容量变大，思路都一样，就是说法不一样