首发于范浩博科学院自如公寓门口，计划在入口处用砖砌一个水库。从上面看凹凸不平，凹进去的地方会有水。那么如果把每块砖的高度用一个数字来表示，就形成了一个二维数据（比如例子）。这个水池可以储存多少单位的水？例如，当二维数组为：999930097826时，答案是中间的0,0位置可以存储2（因为最外面是2）个单位的水，所以答案是2+2=4。示例：输入：[1111,1001,1111]输出：2输入：[121112013,12981212,13100315,1944715,1943015,1213101513]输出：58条解题思路这道题是所有题中让我疑惑时间最长的一道。一开始，我的思路被禁锢了，想直接求出每块砖的有效最小砖高度$H_{min}$，那么这块砖的剩余水量为$w[i][j]=H_{min}-h[i][j]$($h[i][j]$是砖块的高度，i和j是砖块的位置坐标)，所以蓄水池能存的水是$\sum_{i=1}^n\sum_{j=1}^nw[i][j]$。经过一番尝试，我发现围绕某块砖寻找最低有效砖的逻辑复杂且难以理解。我也尝试过使用回溯算法找到池中的所有连通图，但没有结果。最后发现一个基础平台的同学实现思路很清晰。我觉得他的实现是最合适的，于是研究了一下。在这个实现中，巧妙地运用了逆向思维。首先将水池注满水（最高砖块的高度），然后通过条件判断每块砖块是否需要漏水，直到没有需要漏水的砖块为止。实现思路如下：找到高度最高的砖块，记录高度为$H_{max}$；对去除边界的砖块进行注水操作，每块砖块的注水量为$w[i][j]=H_{max}-h[i][j]$($h[i][j]$是砖块的高度）；对某块砖进行漏水操作，只要砖的高度和持水量之和小于砖的高度和持水量之和，则需要漏水。漏水情况可以描述为$w[i][j]>0$&&$h[i][j-1]+w[i][j-1]row=count($data);$this->col=count($data[0]);foreach($dataas$row=>$rowArray){foreach($rowArrayas$col=>$height){$height=(int)$height;$this->gridArray[$row][$col]['height']=$height;$this->gridArray[$row][$col]['water']=0;//获取最高砖的高度if($this->maxHeight<$height){$this->maxHeight=$height;}}}}//判断是否是池边publicfunctionisBorder($row,$col){if($row==0||$row==$this->row-1||$col==0||$col==$this->col-1){返回真；}返回假；}民众函数运行（）{$this->addWater();while($this->removeWater());返回$this->collect();}}注水操作：publicfunctionaddWater(){foreach($this->gridArrayas$row=>$rowArray){foreach($rowArrayas$col=>$grid){if(!$this->isBorder($行,$col)){$this->gridArray[$row][$col]['water']=$this->maxHeight-$this->gridArray[$row][$col]['height'];}}}}漏水操作：publicfunctionremoveWater(){foreach($this->gridArrayas$row=>$rowArray){foreach($rowArrayas$col=>$grid){if($this->canRemove($row,$col)){返回真;}}}returnfalse;}漏水条实际上如下：publicfunctioncanRemove($row,$col){$can=false;if($this->gridArray[$row][$col]['water']>0){//上if($this->gridArray[$row][$col]['water']+$this->gridArray[$row][$col]['heright']>$this->gridArray[$row-1][$col]['water']+$this->gridArray[$row-1][$col]['height']){$this->gridArray[$row][$col]['water']=$this->gridArray[$row-1][$col]['water']+$this->gridArray[$row-1][$col]['height']-$this->gridArray[$row][$col]['height'];如果（$this->gridArray[$row][$col]['water']<0）{$this->gridArray[$row][$col]['water']=0;}$可以=真；}//右if($this->gridArray[$row][$col]['water']+$this->gridArray[$row][$col]['height']>$this->gridArray[$row][$col+1]['water']+$this->gridArray[$row][$col+1]['height']){$this->gridArray[$row][$col]['water']=$this->gridArray[$row][$col+1]['water']+$this->gridArray[$row][$col+1]['height']-$this->gridArray[$row][$col]['height'];如果（$this->gridArray[$row][$col]['water']<0）{$this->gridArray[$row][$col]['water']=0;}$可以=真；}//下if($this->gridArray[$row][$col]['water']+$this->gridArray[$row][$col]['height']>$this->gridArray[$row+1][$col]['water']+$this->gridArray[$row+1][$col]['height']){$this->gridArray[$row][$col]['water']=$this->gridArray[$row+1][$col]['water']+$this->gridArray[$row+1][$col]['height']-$this->gridArray[$row][$col]['height'];如果（$this->gridArray[$row][$col]['water']<0）{$this->gridArray[$row][$col]['water']=0;}$可以=真；}//左if($this->gridArray[$row][$col]['water']+$this->gridArray[$row][$col]['height']>$this->gridArray[$row][$col-1]['water']+$this->gridArray[$row][$col-1]['height']){$this->gridArray[$row][$col]['water']=$this->gridArray[$row][$col-1]['water']+$this->gridArray[$row][$col-1]['height']-$this->gridArray[$row][$col]['height'];如果（$this->gridArray[$row][$col]['water']<0）{$this->gridArray[$row][$col]['water']=0;}$可以=真；}}return$can;}连续漏水操作：publicfunctionrun(){while($this->removeWater());}积木积水量求和：publicfunctioncollect(){$sum=0;foreach($this->gridArrayas$row=>$rowArray){foreach($rowArrayas$col=>$grid){$sum+=$grid['water'];}}return$sum;}接收标准输入处理并输出结果：$filter=function($value){returnexplode('',$value);};$pool=newPool(array_map($filter,explode(',',$input)));echo$pool->run(),PHP_EOL;类似题推特之前也写过类似水库的试题，不过这道题是三维池（二维数组），Twitterreservoir笔试题为平池（一维数组），降低了解题的复杂度。当然推特水库笔试题也可以用这道题的思路来实现，但是时间复杂度是$O(n^2)$，我推特技术面试失败的实现时间复杂度是$O(n)$。实现思路如下：首先用两个指针（left和right）分别指向数组的第一个元素和最后一个元素，左指针从左向右遍历，右指针从右向遍历左边;初始化数组中的一个元素（a[0]）为左遍历得到的最大值（max_left），最后一个元素（a[a.length-1]）为右遍历得到的最大值（max_right）遍历；开始遍历，遍历结束条件为左指针不小于右指针；如果左遍历的最大值小于右遍历的最大值，说明只要有沟（即小于左边最大值max_left的元素）就会有积水，因为右边的最大值可以保证左边沟里的积水不会流失；同理，如果左边遍历的最大值不小于右边遍历的最大值，则只要有沟就会有水（即右边小于最大值max_right的元素）;具体实现可以直接参考CuGBabyBeaR一文。总结一下这道题的水库问题，如果理解了问题的本质，逆向思考，把寻找某块砖周围的最小有效砖高度（寻找有效砖涉及到边界扩散）转化为判断某块砖是否需要漏水条件，那么这个问题就简化了很多，那么后面的编码就容易实现了，本文算法的时间复杂度为$O(n^3)$。相关文章?王者编程大赛之一(2017-12-05)【王者编程大赛3-01背包】(https://www.fanhaobai.com/201...(2017-12-05)王者编程大赛第四场-JosephRing(2017-12-06)编程之王第五场-最短路径(2017-12-06)
