2019-12-13 吴亲库里 库里的深夜食堂
这道题挺有趣的，其实就是让你求最大能盛水的面积。面积就不用我说了吧。两个柱子之间的最低高度乘以他们的距离。图中两个红线之间就是他们能盛水的最大面积。
****
第一时间想到的是暴力破解。两层for循环，遍历出所有的情况，用一个变量来更新最大面积，在数据量多且数值大的情况下，也成功的超时了。。。。这里时间复杂度O(n*n)，我们需要做的是咋么调高运行效率
/**
* @param Integer[] $height
* @return Integer
*/
function maxArea($height) {
$res=0;
for($i=0;$i<count($height);$i++){
for($j=$i+1;$j<count($height);$j++){
$res=max($res,min($height[$i],$height[$j])*($j-$i));
}
}
return $res;
} 
再想一下，面积的大小是由高度和长度所决定的，任意一个要点的长度都决定面积的大小，假设我们现在设置两个点，一个在数组最前面，一个在数组最后面，说白点此时形成了长度最长的情况。先更新此时的最大面积，我们可以拿图参考，开头黑色的高度是1，末尾是7，他们长度是8，所以此时最大盛水面积是1*8=8。然后缩小长度，关键点在于我们应该移动高度高的，还是移动低的? 很简单的道理，因为不管移动哪边，长度始终在减一位，这个条件是不变的，剩下的面积大小完全取决于高度的变化，如果移动了高的那边，面积的区域会受限于较低的那个高度而不会增加面积，而移动低位可以调整最低高度的值，从而在相同的条件下(长度变短)，但面积能增大。这也叫双指针法。这里的时间复杂度是O(n),其中n表示数组的长度。
/**
* @param Integer[] $height
* @return Integer
*/
function maxArea($height) {
$res=0;
$start=0;
$end=count($height)-1;
while($start<$end){
$res=max($res,min($height[$start],$height[$end])*($end-$start));
$height[$start]<$height[$end]?$start++:$end--;
}
return $res;
}
