☆打卡算法☆LeetCode 11、盛最多水的容器 算法解析
☆打卡算法☆LeetCode 11、盛最多水的容器 算法解析
一、题目
1、算法题目
“根据输入的数组数字构建坐标轴，求出坐标轴构成的容器可以容纳最多的水。”
题目链接： 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water/
2、题目描述
给你 n 个非负整数 **a1，a2，...，an**，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (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)
只需要额外的常数级别的空间。
三、总结
说实话，解这道题之前连双指针是啥都不知道，所以就想不到用双指针，对于刷题来说，多吸取别人的优秀的解题思路，并且理解与实现是很重要的。
所谓的解题思路，就是你解题解的多了，当然就有思路了。对于有些题目的解题思路不会就是不会，也不是努力思考就能想出来的，所以，这就是刷题的意义，这种题目刷多了，将题目进行总结归纳，这些巧妙的思想我们自然就可以学会了。
所以，总结一下双指针思想，最重要的一点就是，双指针大多都是对双层循环的优化，所以当使用暴力解题法双层遍历循环的时候，就可以想一下是否可以使用双指针去解题。
其次，就是双指针的限制的满足条件，必须根据题目找到这个限制条件，这个条件也是双指针的移动条件，也是双指针的思想的基础。