如何编写代码实现盛最多水的容器

这篇文章主要讲解了“如何编写代码实现盛最多水的容器”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何编写代码实现盛最多水的容器”吧！

题目

盛最多水的容器

描述

难度：中等

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

说明：你不能倾斜容器

输入：[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：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

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

提示

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

Solution

暴力解法

解题思路

如何求最多的水

求最多的水，本质上是求两个垂直线在二维坐标轴上组成的面积大小，根据木桶原理，能装多少水取决于它最短的那块木板，设定x，y作为两个线的下标，对应height[x]，height[y]作为对应xy的高度整体最终两个垂直线求得的面积公式为

abs(y-x) * min(height[x],height[y])

通过暴力双重FOR循环，可以很快解出此题，依次算出每个垂直线跟其他垂直线组成的面积大小，超过当前最大面积则替换，循环完后得出最大面积

CODE

class Solution {
    public int maxArea(int[] height) {
        //  (y-x)* min(ax,ay)
        if(height.length <= 1) return 0;
        int res = 0;//保存结果
        for(int i = 0; i < height.length - 1; i++)//以i为左挡板，从O开始
        {
            for(int j = height.length - 1; j > i; j--)//以j为右挡板，从height.length - 1开始
            {
                int L = j - i;//底边长度
                int H = Math.min(height[i], height[j]);//对短的板子为高
                res = Math.max(res, L * H);//取最大值
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度 O(N^2) 你有你的双指针，我有我的FOR循环

结果

• 超时，之前还没有超时，现在提交已经显示超时...

双指针

解题思路

我们可以设定两个指针来分别指定整个height的全部，指针x初始指定最左侧坐标，指针y初始指定最右侧坐标

我们需要不断移动指针X或者Y，求取对应XY的面积，直到X指针和Y指针相等则面积计算结束

abs(y-x) * min(height[x],height[y])

回到我们上面的面积计算公式，其中可以拆解为两部分

• abs(y-x)

• min(height[x],height[y])

这里面有一个隐藏的条件公式

• 移动X，X=X+1

• 移动Y，Y=Y-1

对应abs(y-x)，无论移动X或者Y，对应abs(y-x)的值是不变的

• 移动X，abs(y-(x+1)) = abs(y-x-1)

• 移动Y，abs((y-1)-x) = abs(y-x-1)

对应min(height[x],height[y])

• 如果移动height[x],height[y]中的最大值，则 min(height[x],height[y])的值可能不变或者变小

• 不变，新的最大值 > = 现有最小值

• 变小，新的最大值 < 现有最小值

• 如果移动height[x],height[y]中的最小值，则 min(height[x],height[y])的值可能变小，不变或者变大

• 变小，新的最小值 < 现有最小值

• 不变，新的最小值 = 现有最小值

• 变大，新的最小值 > 现有最小值

在既有情况下，选择变大方向是计算更大面积的唯一取法

CODE

class Solution {
    public int maxArea(int[] height) {
      	//长度
        int length = height.length ;
      	//左侧指针
        int x = 0 ;
        //右侧指针
        int y = length - 1;
        //最大面积
        int res = 0;
        while(x!=y){
            //取两个指针中最小的高度
            int minHeight = Math.min(height[x],height[y]);
            //计算res，取最大
            res = Math.max(res,(y-x)*minHeight);
            //如果x对应的高度 > y对应的高度，则需要移动高度低的指针，即y=y-1
            if(height[x]-height[y] > 0){
                y = y - 1;
            }else{
              //对应x对应的高度 <= y对应的高度，则需要移动高度低的指针，即x=x+1
                x = x + 1;
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(N)，双指针总计最多遍历整个数组一次

• 空间复杂度：O(1)，只需要额外的常数级别的空间

感谢各位的阅读，以上就是“如何编写代码实现盛最多水的容器”的内容了，经过本文的学习后，相信大家对如何编写代码实现盛最多水的容器这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！