最近的大雨總是牽動(dòng)著人們的心。

鄭州的大雨淹了好多地方，上海因?yàn)榕_(tái)風(fēng)而建議周一在家辦公。作為一名軟件工程師，沒(méi)有技能去沖在第一線抗災(zāi)，那么我們就在大后方好好地修煉內(nèi)功，提升自我吧。

今天我們就來(lái)看一道和“雨水”相關(guān)的題目。

題目

輸入：[1,2,3,1,3]

輸出：9

可以想象每一個(gè)數(shù)字是一個(gè)擋板，每個(gè)數(shù)字可保證大于0。

釋義：樣例中每一格可接的雨水分別為1，2，3，3，故輸出為1+2+3+3 = 9

題目討論

這道題目本身還是蠻有意思的，屬于使用代碼去模擬現(xiàn)實(shí)世界并解決其問(wèn)題。這類題目首先要認(rèn)真分析題目，多看一下例子，總結(jié)其規(guī)律，然后再解決即可。

我們以每一格為立足點(diǎn)，來(lái)看哪些因素會(huì)影響其接水量。

對(duì)于第一格來(lái)說(shuō)，它的接水量是1，即左邊的擋板高度為1，右邊的擋板高度為2。因此可以得出結(jié)論：接水量取決于左右擋板中較矮的那一個(gè)。

對(duì)于現(xiàn)實(shí)世界，我們應(yīng)該能比較容易想到另一種情況，即輸入是3，1，3時(shí)，第一格中的接水量應(yīng)該為3，而不是取兩個(gè)擋板的最小值1。因?yàn)槿绻麅蓚?cè)有更高的擋板，那么此時(shí)會(huì)“淹掉”較矮的擋板，而接水量取決于左右兩側(cè)最高的擋板。所以這里需要修改一下上面的結(jié)論。修改成什么樣呢？這里建議讀者可以自己先想一下。

。。。。。。。。。。

。。自行思考地帶。。

。。。。。。。。。。

好了，我們來(lái)說(shuō)結(jié)論：接水量取決于左邊的最大值和右邊的最大值中的最小值

接水量結(jié)論

好了到這里基本的思路是清晰的，建議讀者可以自己動(dòng)動(dòng)手實(shí)踐一下。

我們知道，代碼是“練”會(huì)的，不是“看”會(huì)的。

。。。。。。。。。。

。。自行實(shí)踐地帶。。

。。。。。。。。。。

完整版代碼

接雨水

可以注意一下數(shù)組方法slice的使用，用以分割數(shù)組。

用法：

[1,2,3,4].slice(0,2)返回 [1,2]，即從0號(hào)下標(biāo)元素開(kāi)始（包含），到2號(hào)下標(biāo)結(jié)束（不包含）的數(shù)組

[1,2,3,4].slice(1)返回 [2,3,4]，即從0號(hào)下標(biāo)素開(kāi)始（包含），到結(jié)尾的數(shù)組

總結(jié)

上述方法的復(fù)雜度分析如下：

時(shí)間復(fù)雜度O(n2)：一層循環(huán)內(nèi)，每次取最大值也是O(n)的復(fù)雜度，因此相當(dāng)于兩層循環(huán)

空間復(fù)雜度O(n)：使用了一個(gè)新數(shù)組來(lái)存每一格的接水量

讀者朋友，你能想到其他更高效或更有趣的解決方法么？

歡迎留言討論