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

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 1、算法题目

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

题目链接：

来源：力扣（LeetCode）

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

### 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、代码实现

双指针法参考代码：

```csharp

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)

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

## 三、总结

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

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

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

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