介紹

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

適合人群：

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

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費您的時間）

過往題目在這里！

滑動窗口的最大值

題目看這里，leetcode第二三九題，hard難度：
https://leetcode.com/problems/sliding-window-maximum/

強烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時回復。做完了歡迎在評論區(qū)打卡～

解析

解法一：

基本上是非常普通的優(yōu)先級隊列應用，注意python里只有最小堆，如果想每次搞定最大的值，需要每次push時加一個負號才行。另一個易錯點在于，堆里的值可能會過期，當它過期時要及時去除，這就要求我們同時把元素的位置也壓入堆中。

解法二：

這是使用單調(diào)隊列的最優(yōu)解，說實話我一開始沒想出來，太難力。雙端隊列這一點尤其難想。不過仔細考慮，入隊的時候，如果前面還有比當前值小的元素，那一定要把那些元素彈出。既然我們要入隊位置i的元素，那說明滑動窗口已經(jīng)到了i這個地方。有兩種情況，第一種情況是，i之前的隊列中已經(jīng)沒有比i位置還大的元素，這種情況下我們應該把隊列清空，只留下i位置的元素。第二種情況是，隊列里還有比當前i還大的元素j，不過還沒過期，那么我們應該返回j元素。等到j元素過期，我們選最大元素的時候還是要考慮i位置的元素，而不是那些比i小的排在i前面的元素，那些元素在i出現(xiàn)時就已經(jīng)沒用了。

最近如果可以，我選一些單調(diào)隊列的題目來做做看。

思考樂園

對于解答一：

1. my_heap[0][1] <= i-k, 這里為什么不是<而是<=？

2. 在第二個for循環(huán)中，如果我們每次都push一個再pop一個，那么堆里不就一直是k個元素嗎？這樣k個元素的最大堆，始終會返回其中最大的元素。請問可以這樣做嗎？為什么可以或者不可以？（<-筆者最討厭的問問題的方式之一，看起來就是不會的感覺）

歡迎把答案寫在評論區(qū)。

音樂推薦

今天依舊是不知道吃什么的一天，去墨西哥餐廳進行了新一輪的抽獎，依舊是先點菜再查意思。這次選了quesabirria（墨西哥炸玉米餅）。從菜單的圖片看，外表只是平平無奇的玉米餅，但是實際到手發(fā)現(xiàn)中間夾了醬牛肉，味道相當不錯。那么今天的音樂推薦是，同樣封面平平無奇，實際上卻意外好聽的性空山，來自安婧_Tiffany。說起來，打了這么多次ttup的廣告，什么時候小羅的米才能到賬?。ㄩ_玩笑，并沒有這種東西??）

教材鏈接

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