台阶积水问题

数组中的每一个元素相当于一个台阶，假使水量足够大，那么台阶上的积水有多少，例如数组[0,1,0,1,2,1,0,1,3,2,1,2,1]的台阶积水量为6，示例图如下：

image.png

思路：模拟下雨，最低洼的地方最先积水，如1区域先积满水，然后2区域再积满水

先计算出所有的台阶分类，从小到大排序，
遍历台阶分类，找到每一级台阶之间的洼地，然后积水(使积水 与该级台阶持平)，然后对更上一级台阶之间的洼地积水，以此类推

寻找洼地就是寻找该级台阶在数组中第一次以及最后一次出现的位置，针对两者之间低于该级的台阶进行积水

Code:

<?php

/**
 * 台阶积水问题
 * 数组中的每一个元素相当于一个台阶，
 * 假使水量足够大，那么台阶上的积水有多少，
 * 例如数组[0,1,0,1,2,1,0,1,3,2,1,2,1]的台阶积水量为6
 */

$arr = [0,1,0,1,2,1,0,1,3,2,1,2,1];

function arrayPool(Array $arr) :Int {
    $beforeRain = array_sum($arr);
    $arr2 = array_unique($arr);//所有台阶的大小分类
    sort($arr2);
    //只有同一级台阶或没有台阶，则无法积水
    if(count($arr2) <= 1){
        return 0;
    }

    //忽略0级台阶
    if($arr2[0] == 0){
        array_shift($arr2);
    }

    $rArr = array_reverse($arr, true);//为了方便查找台阶最后出现的位置 
    foreach($arr2 as $a){
        $left = array_search($a, $arr);//该级台阶第一次出现的位置
        $right  = array_search($a, $rArr);//最后出现的位置
        for($i = $left + 1; $i < $right; $i++){
            if($arr[$i] < $a){
                $arr[$i] = $a;
            }
        }
    }

    $afterRain = array_sum($arr);
    $pool = $afterRain - $beforeRain;
    return $pool;
}

echo arrayPool($arr);

个人想法请多指教