LeetCode每日一题，盛最多水的容器

题目

盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：中等

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

说明：你不能倾斜容器

img

输入：[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初始指定最右侧坐标

image-20210419224605310

我们需要不断移动指针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)，只需要额外的常数级别的空间

结果

• 执行用时：5 ms, 在所有 Java 提交中击败了46.01%的用户

• 内存消耗：51.9 MB, 在所有 Java 提交中击败了26.93%的用户

断剑重铸之刃，骑士归来之时