条垂线#xff0c;第

[1,8,6,2,5,4,8,3,7]。

在此情况下容器能够容纳水表示为蓝色部分的最大值为

输入height

从下标0开始把所有情况全部算出来求最大及其原始暴力的方法作为一个学习算法和编程的人首先排除此方法。

二、双指针

此类型题目可以理解为日常生活中所说的木桶效应一个木桶能装多少水是由最短的那块板子来决定的同样在计算容积时高是由最短的那个数来决定的而想要从数组中找出最优解枚举是不可缺少的但要尽可能的控制枚举的次数从而降低代码的时间复杂度。

用h表示高w表示宽

从中间随机截取一段来举例[6,2,5,4]首先可以算出体积为3*412现在假设拿4依次根其他几个数作枚举w无疑是在减小的那么现在会出现两种情况

2.h比4大那高度还得是4所以和刚开始比h不变w减小容积量在减小。

所以当在一个区间内选最左和最右两个数算出容积之后两个数中小的那个数已经完全没有必要再去向内进行枚举了因为无论怎么枚举容量都是变小的。

此时4可以直接不考虑了。

我们可以知道容量是受宽和高的影响的而我们需要找出的就是一个宽和高都相对较高的值结合上面的分析所以为了加快效率两个指针一个在前一个在后同时由外向内进行遍历可以大大节约时间那边小直接向内移动那边然后计算容量这样就可以用O(n)的时间复杂度来找出最大容量了。

扩大到整个数组最左最右计算完直接干掉1向右移继续找如果比之前算出来的都大就更新max。

class

max0,h0,w0;while(leftright){wright-left;if(height[left]height[right])

hheight[left];else