☆打卡算法☆LeetCode 11、盛最多水的容器 算法解析

一、题目

1、算法题目

“根据输入的数组数字构建坐标轴，求出坐标轴构成的容器可以容纳最多的水。”

题目链接： 来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/co…

2、题目描述

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

说明：你不能倾斜容器。

示例 1：

输入：height = [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 = [1,2,1]
输出：2
复制代码

示例 4：
输入：height = [4,3,2,1,4]
输出：16
复制代码

二、解题

1、思路分析

这道题，最优做法是使用双指针，在初始时，设两指针i,j分别指向数组的左右两侧,指向的水槽版的高度分别为h[i],h[j]，此时的容量为S[i,j]，因为容量是由两端中的短板决定的，因此可以得到面积公式：

S(i,j) = min(h[i],h[j]) x (j-i)

此时，我们需要去移动指向数字较小的那个指针（容量=两个指针指向的数字中的较小值*指针之间的距离）。

指向数字较大值的此时就可以作为容器的边界，直到移动的指针指向的数大于当前边界，就移动另一个指针。

那么，每次以双指针为左右边界，也就是数组的左右边界 ，计算出容器的最大值。

2、代码实现

双指针法参考代码：

public class Solution 
{
    public int MaxArea(int[] height) 
    {
        int l = 0, r = height.Length - 1, ans = -1, curr = -1;
        while (l <= r) {
            curr = (r - l) * Math.Min(height[l], height[r]);
            ans = Math.Max(curr, ans);
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
}
复制代码

3、时间复杂度

时间复杂度 ： O(N)

双指针总计最多遍历整个数组一次。

空间复杂度： O(1)

只需要额外的常数级别的空间。

三、总结

说实话，解这道题之前连双指针是啥都不知道，所以就想不到用双指针，对于刷题来说，多吸取别人的优秀的解题思路，并且理解与实现是很重要的。

所谓的解题思路，就是你解题解的多了，当然就有思路了。对于有些题目的解题思路不会就是不会，也不是努力思考就能想出来的，所以，这就是刷题的意义，这种题目刷多了，将题目进行总结归纳，这些巧妙的思想我们自然就可以学会了。

所以，总结一下双指针思想，最重要的一点就是，双指针大多都是对双层循环的优化，所以当使用暴力解题法双层遍历循环的时候，就可以想一下是否可以使用双指针去解题。

其次，就是双指针的限制的满足条件，必须根据题目找到这个限制条件，这个条件也是双指针的移动条件，也是双指针的思想的基础。