一周编程集训day3：队列与堆
一周编程集训day3：队列与堆
1 任务
队列与堆：学习队列思想及堆排序思想，并完成leetcode上的返回滑动口中的最大值(239)！并同 时温习前二天内容，做出总结！！
2 概念介绍
-
队列（常用数据结构之一）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 -
堆（Heap）：从根结点开始，每个结点可以有左、右两个结点，元素优先将每一层按从左到右的方式填满，即父结点最多有两个子结点，有右子结点就一定会有左子结点，同一层的某个结点左边一定是填满的。
接下来，说一说堆中元素摆放的规则。堆分为两种情况，有最大堆和最小堆，最小堆就是根结点元素的值是所有元素中最小的，最大堆则相反，下图是一个最小堆。在一个摆放好元素的最小堆中，可以看到，父结点中的元素一定比子结点的元素要小，但对于左右结点的大小则没有规定谁大谁小。接下来，说一说堆中元素摆放的规则。堆分为两种情况，有最大堆和最小堆，最小堆就是根结点元素的值是所有元素中最小的，最大堆则相反，下图是一个最小堆。在一个摆放好元素的最小堆中，可以看到，父结点中的元素一定比子结点的元素要小，但对于左右结点的大小则没有规定谁大谁小。
关于最小堆（最大堆）的常用的操作有插入新元素和取最小值（最大值）。关于最小堆（最大堆）的常用的操作有插入新元素和取最小值（最大值）。
1）插入操作就是直接把新的元素放到最下面一层的可用的最左边，如下图中的X，当X比父结点3要大，那么堆的结构是稳定的，插入操作即完成；如果X比3要小，那么就不符合我们之前说的规则，就要把父结点3和X结点交换，交换完后还没结束，还要比较X和交换完后的父结点即1的大小，如果比1小，则结束，否则仍要继续交换直到稳定。
2）取小值操作，直接将根结点元素返回；此时根结点为空，需要把最后一个叶结点（即结点8）放到根结点的位置，此时把元素8和左右子结点比较小的那一个（即3）作比较，如果比子结点大，则交换，以此累推，直到堆结构稳定。
3 leetcode
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。
python解答思路：一开始没思路，参考了网上思路，给出以下代码解答。
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:return []
res,window = [],[]
for i,x in enumerate(nums):
if i >= k and window[0] <= i - k:
window.pop(0)
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
if i >= k - 1:
res.append(nums[window[0]])
return res
leetcode提交结果：