leetcode分类刷题：队列（Queue）（一、单调队列）

单调队列，看起来是与单调栈对应起来的一样；但是做题的时候感觉单调队列不像单调栈一样，能根据题意自然形成

剑指 Offer 59 - II. 队列的最大值

单调队列的基本实现，感觉单调队列更像是和某个队列对应起来的一样

from collections import deque
'''
剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value需要返回 -1
示例 1:
    输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
    输出:[null,null,null,2,1,2]
思路：单调队列的基本实现
'''


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

    def max_value(self) -> int:
        if len(self.queue) > 0:  # 这里应该判断普通的queue是否为空，它不为空，deque一定不为空
            return self.deque[0]
        else:
            return -1

    def push_back(self, value: int) -> None:
        self.queue.append(value)
        # 保持deque队列单调不增
        while len(self.deque) > 0 and self.deque[-1] < value:  # 访问元素都要确保队列不为空
            self.deque.pop()
        self.deque.append(value)

    def pop_front(self) -> int:
        if len(self.queue) == 0:
            return -1
        else:
            value = self.queue.popleft()
            if value == self.deque[0]:  # 这里的deque是一定有值的，不用判断deque不为空了再访问
                self.deque.popleft()
            return value


if __name__ == "__main__":
    myQueue = MaxQueue()
    myQueue.push_back(1)
    myQueue.push_back(3)
    print(myQueue.pop_front())
    print(myQueue.max_value())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

239. 滑动窗口最大值

1、单调队列的经典题型：使用双向队列维护窗口，窗口移动的元素增删与队列的先进先出思想一致：始终保持队头元素最大、队尾元素最小，恰好形成了单调队列
2、这道题还可以用优先队列求解，感觉优先队列（大顶堆）解决Top K问题的思想与这道题更匹配，细节方面就是要注意堆内添加的元组形式及用索引判断进行持续出堆

from typing import List
from collections import deque
import heapq
'''
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
    输入：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
题眼：滑动窗口中的最大值
思路1、单调队列：使用双向队列维护窗口，窗口移动的元素增删与队列的先进先出思想一致：始终保持队头元素最大、队尾元素最小，恰好形成了单调队列
思路2、优先队列：大顶堆，始终保持窗口内最大元素位于顶部，增加元素入堆，删除元素时持续出堆顶元素
'''


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 思路1、单调队列：使用双向队列维护窗口，窗口移动的元素增删与队列的先进先出思想一致：始终保持队头元素最大、队尾元素最小，恰好形成了单调队列
        que = deque()  # 与栈一样，可以思考下加入队列的是元素还是索引：这道题是都可以，且加入元素更加直观
        # 1、初始化队列
        for i in range(k):
            if len(que) == 0:
                que.append(nums[i])
            else:
                if nums[i] <= que[-1]:
                    que.append(nums[i])
                else:
                    while len(que) > 0 and nums[i] > que[-1]:
                        que.pop()
                    que.append(nums[i])
        result = [que[0]]
        # 2、继续遍历剩余的元素
        for i in range(k, len(nums)):
            # 元素入队：索引为i
            while len(que) > 0 and nums[i] > que[-1]:
                que.pop()
            que.append(nums[i])
            # 元素出队：索引为i-k，也可以先元素入队
            if nums[i - k] == que[0]:
                que.popleft()
            result.append(que[0])
        return result

        # # 思路2、优先队列：大顶堆，始终保持窗口内最大元素位于顶部，增加元素入堆，删除元素时持续出堆顶元素
        # # 1、初始化大顶堆
        # que = []
        # for i in range(k):
        #     heapq.heappush(que, (-nums[i], i))  # heapq.heappush()会自动完成小顶堆的排序
        # result = [-que[0][0]]
        # # 2、继续遍历剩余的元素
        # for i in range(k, len(nums)):
        #     # 元素入队：索引为i
        #     heapq.heappush(que, (-nums[i], i))
        #     # 元素出队：索引为i-k及之前的索引没出的，需要持续出
        #     while que[0][1] <= i - k:
        #         heapq.heappop(que)
        #     result.append(-que[0][0])
        # return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            nums = [int(n) for n in in_line[1].split(']')[0].split('[')[1].split(',')]
            k = int(in_line[2].strip())
            print(obj.maxSlidingWindow(nums, k))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80