【刷题日记】11. 盛最多水的容器
本次刷题日记的第 13 篇，力扣题为：11. 盛最多水的容器 ，中等
一、题目描述：
拿到这道题是啥感受呢？
题目描述没有几个字，看上去好像说的挺清楚的，不就是计算一下容器能容纳的最大水量么，可是咋感觉题目越明确，咱实现起来就约迷糊呢？
没事兄弟们，咱们干就玩了 ，好好分析一下
二、思路分析：
1、这道题考察了什么思想？你的思路是什么？
我们一起来看看这道题给予了我们哪些重要信息：
- 题中会给出一个数组，这个数组元数个数是 2 -- 10 的 5 次方个，意味着我们无需判断入参的数组长度是否是小于 2 的情况
- 将数组转成一个容器，计算宽高，得出容器能容纳最多的水
这有点像木桶效应，一个木桶能够容纳多少水，取决于最短的那一块板子，而此处，容器能容纳多少水，取决于 2 个变量
- 容器的高度
- 容器的宽度
综合来的需要做到 容器的高度 * 容器的宽度 最大
那么我们就来推演一下：
就使用题目给出的示例：[1,8,6,2,5,4,8,3,7]
对于这道题，我们要计算容器最大容纳水的大小，那么我们可以用方框来框选，你是否会这样来框选呢？从左到右依次向右展开来框选
以第一根柱子为准，向右扩展
省略后续步骤 ...
以第二根柱子为准，向右扩展
省略后续步骤 ...
按照上述的方式，固然是可以找到我们期望找的最大的容纳水的数量，可是这种方式时间复杂度太高，必然时候超时的，我们可以换一个思路
既然是找到最大的容纳水的数量，我们是不是可以从有可能是最大的数据边界开始找呢？我们不好控制柱子的高度，但是我们可以控制容器的宽度
因此，我们可以这样来找
- 直接从最左边柱子和最右边柱子作为容器的边界来不断的向中间收拢
- 当需要收拢的时候，从较短的那一边开始收拢，这样就比较容易理解，咱们循环的次数也能大大减少
上图已经明确的模拟边界收拢的过程，剩下的就是咱们一起来实现一下上述的想法了，使用双指针的方法
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，根据题意，咱们此处无需判断给定数组的的长度是否小于 2
func maxArea(height []int) int { // 赋初始值，定位容器的左边界和右边界 （双指针的方法） i , j := 0,len(height) - 1 res := 0 for i<j { // 计算当前边界的容器面积，取决于较矮的一边 res = max(res,(j-i) * min(height[i],height[j])) // 从较短的那一边开始收拢 if height[i] < height[j]{ i++ }else{ j-- } } return res } func max(a,b int)int{ if a>b { return a } return b } func min(a,b int)int{ if a<b { return a } return b }
上述就是根据思路实现的代码，思路清晰了，编码就是一个翻译的过程，考虑好各种场景，咱们实现起来就比较顺畅，可以减少返工和出现 bug 的风险
四、总结：
此处咱们只需要遍历整个数组 1 次，则时间复杂度是 O(n) ， 空间复杂度是 O(1) ，因为我们都是使常数级别的空间消耗
原题地址：11. 盛最多水的容器
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
