编程练习-盛最多水的容器

╰半夏微凉° 2023-08-17 16:57 110阅读 0赞

> 昨晚难得忙的差不多，自己有点时间，做了道中等难度的题

#### 题目—[LeetCode盛最多水的容器][LeetCode] ####

> 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。  
> ![示例图片][question_11.jpg]  
> 图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

*  示例
    
    > 输入: \[1,8,6,2,5,4,8,3,7\]  
    > 输出: 49

以上题目描述就照搬[原文了][LeetCode]

#### 思路 ####

*  思路一：暴力法  
    首先，这道题最容易想到的就是暴力法，即计算每两个之间的盛水量，`1和之后的每一个比较，2和之后的每一个比较，n-1和n比较，即k不和k-1比较`。这样结果肯定是能得到的，但是效率不言而喻，若出现在笔试题中，肯定时间等过不了。  
    来分析一下暴力法的时间复杂度：
    
     *  第一个数和后面n-1个数比较，次数为(n-1)。
     *  第二个数和后面n-2个数比较，次数为(n-2)。
     *  ......
     *  第n-1个数和后面`第n个数`比较，次数为n-(n-1)。  
        $O(N) = n-1 + n-2 + n-3 +,......,+n-(n-1) = (n^2-n)/2$，（还去查了一下等差数列求和，手动捂脸）因此时间复杂度为$O(N^2)$
 *  思路二：双指针法  
    通常在涉及到数组遍历时，能在一次遍历找到结果，是最好的结局，题目需要的是两个下标的数字去求解结果，因此想到双指针的方案，`从左到右i，和从右到左j`。那么问题就在于如何移动下标？其实很容易，当然是移动下标处值较小的下标。  
    来分析一下时间复杂度：
    
     *  无论是左下标移动还是右下标移动，最后都只会遍历一遍数组，因此时间复杂度为$O(N)$

#### 实现（java） ####

*  思路一：暴力法

public static int maxArea(int[] height) {
            int maxWater = 0;
            for(int i = 0; i < height.length -1; i++) {
                for(int j = i+1; j < height.length; j++) {
                    int higth = height[i] < height[j] ? height[i] : height[j];
                    int tempWater = higth * (j - i);
                    if(maxWater < tempWater)
                        maxWater = tempWater;
                }
            }
            return maxWater;
        }

*  思路二：双指针法

public static int maxArea2(int[] height) {
            int maxWater = 0;
            int i = 0, j = height.length - 1;
            int hight = 0;
            int temp = 0;
            while(i != j) {
                hight = height[i] < height[j] ? height[i] : height[j];
                temp = hight * (j - i);
                if(temp > maxWater)
                    maxWater = temp;
                if(height[i] <= height[j]) {
                    i++;
                } else {
                    j--;
                }
            }
            return maxWater;
        }

在上面方法中，没有用到Java的Math类，主要是之前听人说，这些类的使用会使得运行时间变长。所以我为了验证，就有了下面的方法

public static int maxArea3(int[] height) {
            int maxWater = 0;
            int i = 0, j = height.length - 1;
            while(i != j) {
                maxWater = Math.max(maxWater, Math.min(height[i], height[j]) * (j - i));
                if(height[i] <= height[j]){
                    i++;
                }
                else{
                    j--;
                }
            }
            return maxWater;
        }

那么暴力法究竟效率有多低，使用Math类的处理，又和没用Math类的处理方法有何区别？直接上图。  
![效率对比][e9kGtsxwcOQmn2l.png]  
对比发现：

1.  暴力法确实效率低。
2.  使用Math类并不会使得效率有多大的改变，所以以后可以使用这些数学类，减少代码。
    
    #### 最后 ####
    
    > 此致，敬礼

转载于:https://www.cnblogs.com/numen-fan/p/11344185.html

[LeetCode]: https://leetcode-cn.com/problems/container-with-most-water/
[question_11.jpg]: /images/20230809/cc1cc676dd7e4c069c47bb0182c465a5.png
[e9kGtsxwcOQmn2l.png]: https://i.loli.net/2019/08/13/e9kGtsxwcOQmn2l.png