介紹

總而言之是時(shí)候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛(ài)好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過(guò)筆試/面試，總覺(jué)得算法題目想不明白的你。

不適合人群：

算法入門(mén)級(jí)選手（一上來(lái)就做難題可能并不合適，建議首先專(zhuān)注簡(jiǎn)單/中等題目）

非常不適合人群：

算法競(jìng)賽選手（這種小兒科的問(wèn)題完全是在浪費(fèi)您的時(shí)間）

過(guò)往題目在這里！

接雨水

題目看這里，leetcode第四十二題，hard難度：
https://leetcode.com/problems/trapping-rain-water/

強(qiáng)烈建議讀者自己先做（不過(guò)真的會(huì)有讀者嗎，笑），有任何問(wèn)題歡迎在評(píng)論區(qū)討論，up看到了會(huì)及時(shí)回復(fù)。做完了歡迎在評(píng)論區(qū)打卡～

解析

這道題目作為一道經(jīng)典的難度題目，十分值得深入研究。其中的單調(diào)棧雖然一開(kāi)始可能讓人感到陌生，但只要熟悉了這個(gè)概念，其實(shí)并不復(fù)雜。題目的難點(diǎn)主要有兩個(gè)方面。

首先，我們?cè)跅Ｖ写鎯?chǔ)的是數(shù)組元素的索引，而非其實(shí)際的高度。這樣做的原因在于，我們需要用這些索引來(lái)計(jì)算可以?xún)?chǔ)存雨水的區(qū)域的寬度。

其次，理解從棧中取出元素來(lái)獲取左邊界的邏輯是一大難點(diǎn)。如果我們只關(guān)注當(dāng)前棧頂元素的高度，可能會(huì)陷入死胡同。舉例來(lái)說(shuō)，如果當(dāng)前棧頂?shù)母叨仁?，新的高度是5，兩者的索引差為4。如果我們只是簡(jiǎn)單地計(jì)算（5-3）*4，這將導(dǎo)致問(wèn)題——我們?nèi)绾文艽_定在3和5之間的最小高度始終為0呢？因此，我們需要將注意力轉(zhuǎn)向當(dāng)前的高度，并從棧頂向左尋找合適的邊界。這就是這道題目真正困難之處所在。

當(dāng)然了，現(xiàn)代面試應(yīng)該沒(méi)人考這道題目，面試官應(yīng)該默認(rèn)你都背下來(lái)了。不過(guò)還是值得一做。

思考樂(lè)園

如果在獲得儲(chǔ)水池底部之后發(fā)現(xiàn)棧是空的，這代表什么？是否依然應(yīng)該計(jì)算儲(chǔ)水區(qū)域的體積？歡迎把答案寫(xiě)在評(píng)論區(qū)。

音樂(lè)推薦

今天又是躺平的一天......接下來(lái)說(shuō)不定要多在家里遠(yuǎn)程干活，每天花四個(gè)小時(shí)在通勤上再怎么說(shuō)也太讓人疲憊了。這首來(lái)自安婧_Tiffany的阿拉斯加海灣送給因?yàn)槊恐芏畟€(gè)小時(shí)的通勤而疲憊不堪的你，希望你的心靈得到撫慰。

教材鏈接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/