题解 | #滑动窗口的最大值#

class Solution:
    def maxInWindows(self, num: List[int], size: int) -> List[int]:
        if not size or size > len(num):
            return []
        from collections import deque

        # a queue of index that is represent the val in num in descending order
        queue = deque()
        res = []
        for i, val in enumerate(num):
            # if the largest val in queue is getting out of the window, pop it
            if i >= size and i - queue[0] == size:
                queue.popleft()
            # pop the smallest val of the queue untill the last val not smaller than current val
            while queue and val > num[queue[-1]]:
                queue.pop()
            queue.append(i)
            # from index size-1, record the results
            if i >= size - 1:
                res.append(num[queue[0]])
        return res


# IT IS IMPORTANT NOTICE THAT:
# queue record the index
# res record the val, hence use num[idx] when doing the value check