介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

(资料图)

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

滑动窗口的最大值

题目看这里，leetcode第二三九题，hard难度：/problems/sliding-window-maximum/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

解法一：

基本上是非常普通的优先级队列应用，注意python里只有最小堆，如果想每次搞定最大的值，需要每次push时加一个负号才行。另一个易错点在于，堆里的值可能会过期，当它过期时要及时去除，这就要求我们同时把元素的位置也压入堆中。

解法二：

这是使用单调队列的最优解，说实话我一开始没想出来，太难力。双端队列这一点尤其难想。不过仔细考虑，入队的时候，如果前面还有比当前值小的元素，那一定要把那些元素弹出。既然我们要入队位置i的元素，那说明滑动窗口已经到了i这个地方。有两种情况，第一种情况是，i之前的队列中已经没有比i位置还大的元素，这种情况下我们应该把队列清空，只留下i位置的元素。第二种情况是，队列里还有比当前i还大的元素j，不过还没过期，那么我们应该返回j元素。等到j元素过期，我们选最大元素的时候还是要考虑i位置的元素，而不是那些比i小的排在i前面的元素，那些元素在i出现时就已经没用了。

最近如果可以，我选一些单调队列的题目来做做看。

思考乐园

对于解答一：

my_heap[0][1] <= i-k, 这里为什么不是<而是<=？

在第二个for循环中，如果我们每次都push一个再pop一个，那么堆里不就一直是k个元素吗？这样k个元素的最大堆，始终会返回其中最大的元素。请问可以这样做吗？为什么可以或者不可以？（<-笔者最讨厌的问问题的方式之一，看起来就是不会的感觉）

欢迎把答案写在评论区。

音乐推荐

今天依旧是不知道吃什么的一天，去墨西哥餐厅进行了新一轮的抽奖，依旧是先点菜再查意思。这次选了quesabirria（墨西哥炸玉米饼）。从菜单的图片看，外表只是平平无奇的玉米饼，但是实际到手发现中间夹了酱牛肉，味道相当不错。那么今天的音乐推荐是，同样封面平平无奇，实际上却意外好听的性空山，来自安婧_Tiffany。说起来，打了这么多次ttup的广告，什么时候小罗的米才能到账啊（开玩笑，并没有这种东西）