今日任务

1. LeetCode239 滑动窗口最大值
2. LeetCode347 前K个高频元素
3. 栈和队列总结

资料来源

1. 代码随想录 | LeetCode239 滑动窗口最大值
2. 代码随想录 | LeetCode347 前K个高频元素
3. 代码随想录 | 栈和队列总结

1 LeetCode239 滑动窗口最大值

输入：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

输入：nums = [1], k = 1
输出：[1]

解析看最后那一块。

python
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = MonotonousQueue()
        result = [0] * (len(nums) - k + 1)
        for i in range(k - 1):
            queue.append(nums[i])
        for i in range(len(nums) - k + 1):
            queue.append(nums[i + k - 1])
            result[i] = queue.getFirst()
            if nums[i] == queue.getFirst():
                queue.pop(nums[i + k - 1])
        return result


class MonotonousQueue:
    def __len__(self):
        return len(self.queue)

    def __init__(self):
        self.queue = deque()

    def getFirst(self):
        return self.queue[0]

    def pop(self, number: int):
        self.queue.popleft()
        if len(self.queue) > 0:
            while self.queue[0] < number:
                self.queue.popleft()

    def append(self, number: int):
        if len(self.queue) == 0:
            self.queue.append(number)
            return
        while self.queue[-1] < number:
            self.queue.pop()
            if len(self.queue) == 0:
                break
        self.queue.append(number)

2 LeetCode347 前K个高频元素

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

输入: nums = [1], k = 1
输出: [1]

解析看最后那一块。

python
import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = dict()
        for i in nums:
            if i in map.keys():
                map[i] += 1
            else:
                map[i] = 1

        pri_que = []

        for key, freq in map.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k:
                heapq.heappop(pri_que)

        result = []
        for i in pri_que:
            result.append(i[1])
        return result

3 栈和队列总结

3.1 栈题目

栈的先进后出的特性，使得它能够快速的解决一些邻近的捉对问题，比如说之前的查括号是否都是一对一对的，或者说删除相邻相同字符。另外在一些要保留之前元素顺序的同时对当前元素和之前的若干个元素进行处理的话，栈也是值得考虑的一种解法，就比如之前的逆波兰表达式。

栈在一些比较底层的程序应用上常见，比如说解析文件路径，再比如说程序运行的函数调用栈。

3.2 队列题目

先说单调队列。

单调队列是一个视情况而定的队列，它的目的一般是使队列里的元素递增或者递减。单调队列并没有一种固定的实现，甚至并不固定是先出先进还是先出后进，根据题目要求来灵活制定pop和append的行为。以今天的题目为例，它就维护了一个名为单调队列，实则为双端队列的数据结构。

这题目要求求滑动窗口中的最大值，那么很明显是要维护一个递减的单调序列，每次要实际求的是最大值。对应到具体的单调队列上，append元素之前就要保证之前的所有元素都比自己大，所以append的行为就是从队列右端一个一个取值和要加入的元素进行比较，直到前面的元素都比自己大为止；pop元素就是要在窗口滑出最大值的时候再pop。

再说大小顶堆/优先级队列。

它和单调队列不一样，单调队列的目的是保证每次pop元素的时候一定pop出最大/最小的那个，而优先级队列则是真的要对元素全部排序。堆对应的是完全二叉树，大顶堆对应的是根节点是最大值，队列就是降序排列；小顶堆对应的根节点是最小值，队列就是升序排序。

最后是python里小顶堆对应的库heapq的用法。

• 建立堆：heap = [] 就使用列表就可以
• 将一个队列加入堆/变成小顶堆：heappush(heap, array)/heapify(heap)
• 弹出元素：heappop(heap)
• 获取堆中前num个的最大值/最小值：nlargest(num, heap)/nsmallest(num, heap)
• 合并两个有序数组：merge(sorted(array1), sorted(array2))
• 先加入num元素，再弹出堆顶元素：heapqpushpop(heap, num)
• 先弹出堆顶元素，再加入num元素：heapqreplace(heap, num)