Day03 堆与对列+LeetCode239

对列
栈和对列都是动态集合，栈是后进先出（LIFO），对列是先进先出（FIFO）

堆
堆是一种完全二叉树，分为大根堆和小根堆。具体参照（堆排序的Python实现(附详细过程图和讲解)）

LeetCode239 滑动窗口最大值

Day03 堆与对列+LeetCode239
刚开始拿到题目，感觉用堆用双向对列都可以做，但是又具体写不出来，于是搜集大佬们的解法，发现我只是有这个想法，却不知道怎么解决，看大佬们的思路也特别费脑，尤其是双向对列的解法，到现在也没理解。。。。堆排序的方法感觉很好理解，但自己却实现不出来（心碎），最后看了Deng同学的解法，感觉恍然大悟，原来还可以有这么简单的解法！！真是给我这种编程小白的一剂良药，遂最终借鉴了Deng同学的解法（附上链接：https://blog.****.net/weixin_39441762/article/details/86674667）也算是拯救了崩溃边缘的我吧。。。。
代码：

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if nums:
            return[max(nums[i:i+k]) for i in range(len(nums)-k+1)]
        else:
            return nums

哈哈哈，是不是超级简单，很好理解！！当然用时较久
Day03 堆与对列+LeetCode239
再简单阐述一下我想用的堆排序但是一直实现不出来的方法：
思想也很简单：创建一个k大小的最大堆，弹出最大值，放入新值，再调整成最大堆，继续弹出。。。。
当然大佬们的叫法是优先队列

Day03 堆与对列+LeetCode239
还有另外一种思想用的双向对列（虽然我现在也没搞清楚）

Day03 堆与对列+LeetCode239
参考资料：
[Leetcode] Sliding Window Maximum 滑动窗口最大值（上述两种解法（优先队列和双向对列来源））
Sliding Window Maximum 固定的滑动窗口里找最大值（优先队列解法）
[LeetCode 239. 滑动窗口最大值]（优先队列）
浅谈算法和数据结构: 五优先级队列与堆排序
 玩转数据结构之优先队列(PriorityQueue)和堆(Heap)
LeetCode 239. Sliding Window Maximum（滑动窗口最大值）（4种解法）
python模块学习（queue模块的Queue类、PriorityQueue类和LifoQueue类）
用Python实现一个优先级队列（Priority Queue）

Day03 堆与对列+LeetCode239

相关推荐