摘要：相關(guān)文章王者編程大賽之一王者編程大賽之三背包王者編程大賽之四約瑟夫環(huán)王者編程大賽之五最短路徑

首發(fā)于 樊浩柏科學(xué)院

自如寓打算門口用磚頭圍立一個蓄水池子，從上面看凹凸不平，凹的地方會有積水。那如果用數(shù)字代表每個磚頭的高度，就形成一個二維數(shù)據(jù)（如示例），請問這個池子能存儲多少單位的水？

例如二維數(shù)組為：

9 9 9 9
3 0 0 9
7 8 2 6
時，答案是中間的 0,0 位置可以存儲 2（因為其外面最低是 2）個單位的水，因此答案為 2 + 2 = 4。

示例：
輸入：[1 1 1 1,1 0 0 1,1 1 1 1]
輸出：2
輸入：[12 11 12 0 13,12 9 8 12 12,13 10 0 3 15,19 4 4 7 15,19 4 3 0 15,12 13 10 15 13]
輸出：58

這道題是所有題中困惑我時間最長的題，一開始思維禁錮在想直接通過找到每塊磚的四周有效最低磚高度 $H_{min}$，然后這塊磚所剩的水為 $w[i][j] = H_{min}-h[i][j]$($h[i][j]$ 為磚的高度，i 和 j 為磚的位置坐標(biāo))，因此蓄水池能蓄下的水為 $sum_{i=1}^nsum_{j=1}^n w[i][j]$。經(jīng)過一番嘗試，發(fā)現(xiàn)尋找某塊磚四周最低有效磚邏輯比較復(fù)雜，且不易理解，又嘗試過使用回溯算法尋找出池子中的所有連通圖，但是也未有果。

最后，發(fā)現(xiàn)基礎(chǔ)平臺一位同學(xué)的實現(xiàn)思路很清晰，我認(rèn)為他的實現(xiàn)是最合適的，所以研究了一下。該實現(xiàn)中機(jī)智地采用逆向思維，首先往池子注滿水（最高磚的高度），然后再通過條件判定每塊磚是否需要進(jìn)行漏水，一直到?jīng)]有磚需要進(jìn)行漏水操作。

實現(xiàn)思路如下：

找出高度最高的磚，高度記為 $H_{max}$；

對除去邊界的磚進(jìn)行注水操作，每塊磚加水量為 $w[i][j] = H_{max} - h[i][j]$（$h[i][j]$ 為磚的高度）；

對某塊磚進(jìn)行漏水操作，只要這塊磚有盛水且上下左右相鄰的 4 塊磚高度和盛水量之和小于這塊磚高度和盛水量之和，則需要進(jìn)行一次漏水，漏水條件可以描述為 $w[i][j] > 0$ && $h[i][j-1] + w[i][j-1] < h[i][j] + w[i][j]$（該條件為磚左側(cè)相鄰的漏水條件，右、上、下同理可得）；

持續(xù)漏水操作，一直重復(fù)步驟 3 直至沒有磚需要進(jìn)行漏水操作；

求和磚的盛水量，$sum_{i=1}^nsum_{j=1}^n w[i][j]$ 即為水池的蓄水量；

算法流程圖示如下：

實現(xiàn)的類結(jié)構(gòu)如下，特殊的方法已提取出，并將一一詳細(xì)說明。

row = count($data);
        $this->col = count($data[0]);

        foreach ($data as $row => $rowArray) {
            foreach ($rowArray as $col => $height) {
                $height = (int)$height;
                $this->gridArray[$row][$col]["height"] = $height;
                $this->gridArray[$row][$col]["water"] = 0;
                //獲取最高磚的高度
                if ($this->maxHeight < $height) {
                    $this->maxHeight = $height;
                }
            }
        }
    }
    
    //判斷是否是水池邊界
    public function isBorder($row, $col)
    {
        if ($row == 0
            || $row == $this->row - 1
            || $col == 0
            || $col == $this->col - 1
        ) {
            return true;
        }

        return false;
    }

    public function run()
    {
        $this->addWater();

        while ($this->removeWater()) ;

        return $this->collect();
    }
}

注水操作：

public function addWater()
{
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            if (!$this->isBorder($row, $col)) {
                $this->gridArray[$row][$col]["water"] = $this->maxHeight - $this->gridArray[$row][$col]["height"];
            }
        }
    }
}

漏水操作：

public function removeWater()
{
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            if ($this->canRemove($row, $col)) {
                return true;
            }
        }
    }

    return false;
}

漏水條件實現(xiàn)如下：

public function canRemove($row, $col)
{
    $can = false;

    if ($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"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //右
        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"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //下
        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"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
        //左
        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"];
            if ($this->gridArray[$row][$col]["water"] < 0) {
                $this->gridArray[$row][$col]["water"] = 0;
            }
            $can = true;
        }
    }

    return $can;
}

持續(xù)漏水操作：

public function run()
{
    while ($this->removeWater()) ;
}

求和磚的盛水量：

public function collect()
{
    $sum = 0;
    foreach ($this->gridArray as $row => $rowArray) {
        foreach ($rowArray as $col => $grid) {
            $sum += $grid["water"];
        }
    }

    return $sum;
}

接收標(biāo)準(zhǔn)輸入處理并輸出結(jié)果：

$filter = function ($value) {
    return explode(" ", $value);
};

$pool = new Pool(array_map($filter, explode(",", $input)));
echo $pool->run(), PHP_EOL;

Twitter 之前曾經(jīng)出過類似蓄水池的筆試題，只不過本題是立體水池（二維數(shù)組），Twitter 蓄水池筆試題是平面水池（一維數(shù)組），解題復(fù)雜度也就降低了，當(dāng)然 Twitter 蓄水池筆試題也可以采用本題的思想來實現(xiàn)，但是時間復(fù)雜度為 $O(n^2)$，采用 我的Twitter技術(shù)面試失敗了 的實現(xiàn)時間復(fù)雜度為 $O(n)$。

實現(xiàn)思路如下：

首先，用兩個指針（left 和 right）分別指向數(shù)組的第一個元素和最后一個元素，左指針從左向右遍歷，右指針從右向左遍歷；

初始化數(shù)組中一個元素（a[0]）為左邊遍歷得到的最大值（max_left），最后一個元素（a[a.length-1]）為從右邊遍歷得到的最大值（max_right）；

開始遍歷，遍歷結(jié)束條件為 左指針不小于右指針；

如果左邊遍歷的最大值小于右邊遍歷的最大值，說明只要有水溝（即小于左邊最大值 max_left 的元素）就會有積水，因為右邊的最大值可以保證左邊水溝的積水不會流失掉；同樣，如果左邊遍歷的最大值不小于右邊遍歷的最大值，只要右邊有水溝（即小于右邊最大值 max_right 的元素）就會有積水；

具體實現(xiàn)，請直接參考 CuGBabyBeaR 文章。

本題的蓄水池問題，如果理解了問題本質(zhì)并逆向思維，將尋找某塊磚四周最低有效磚高度（尋找有效磚涉及到邊界擴(kuò)散）轉(zhuǎn)化為判斷某塊磚是否需要漏水條件，那么問題就簡化很多了，那后續(xù)編碼也就很容易實現(xiàn)了，本文算法的時間復(fù)雜度為 $O(n^3)$。

相關(guān)文章 ?

王者編程大賽之一（2017-12-05）

[王者編程大賽之三 — 01背包](https://www.fanhaobai.com/201...

（2017-12-05）

王者編程大賽之四 — 約瑟夫環(huán)（2017-12-06）

王者編程大賽之五 — 最短路徑（2017-12-06）