數(shù)組中的每一個(gè)元素相當(dāng)于一個(gè)臺(tái)階，假使水量足夠大，那么臺(tái)階上的積水有多少，例如數(shù)組[0,1,0,1,2,1,0,1,3,2,1,2,1]的臺(tái)階積水量為6，示例圖如下：

image.png

思路：模擬下雨，最低洼的地方最先積水，如1區(qū)域先積滿水，然后2區(qū)域再積滿水

先計(jì)算出所有的臺(tái)階分類，從小到大排序，
遍歷臺(tái)階分類，找到每一級(jí)臺(tái)階之間的洼地，然后積水(使積水 與該級(jí)臺(tái)階持平)，然后對(duì)更上一級(jí)臺(tái)階之間的洼地積水，以此類推

尋找洼地就是尋找該級(jí)臺(tái)階在數(shù)組中第一次以及最后一次出現(xiàn)的位置，針對(duì)兩者之間低于該級(jí)的臺(tái)階進(jìn)行積水

Code:

<?php

/**
 * 臺(tái)階積水問題
 * 數(shù)組中的每一個(gè)元素相當(dāng)于一個(gè)臺(tái)階，
 * 假使水量足夠大，那么臺(tái)階上的積水有多少，
 * 例如數(shù)組[0,1,0,1,2,1,0,1,3,2,1,2,1]的臺(tái)階積水量為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);//所有臺(tái)階的大小分類
    sort($arr2);
    //只有同一級(jí)臺(tái)階或沒有臺(tái)階，則無法積水
    if(count($arr2) <= 1){
        return 0;
    }

    //忽略0級(jí)臺(tái)階
    if($arr2[0] == 0){
        array_shift($arr2);
    }

    $rArr = array_reverse($arr, true);//為了方便查找臺(tái)階最后出現(xiàn)的位置 
    foreach($arr2 as $a){
        $left = array_search($a, $arr);//該級(jí)臺(tái)階第一次出現(xiàn)的位置
        $right  = array_search($a, $rArr);//最后出現(xiàn)的位置
        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);

個(gè)人想法請(qǐng)多指教