滑动窗口的最大值

滑动窗口的最大值_牛客题霸_牛客网

问题简述

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
窗口大于数组长度或窗口长度为 0 的时候，返回空。

思路1：优先队列

• 使用优先队列(堆)维护窗口内的最大值;

• 细节:

  • 堆除了要保存值还要保存索引, 用于判断当前的最大值是否还在窗口内;

  • Python 中的默认实现为最小堆, 需要转成最大堆(取相反数);

Python

class Solution:
    def maxInWindows(self , arr: List[int], size: int) -> List[int]:

        if size <= 0 or size > len(arr): return []
        
        import heapq

        # 初始化大顶堆
        h = []
        for i in range(size):
            heapq.heappush(h, (-arr[i], i))  # 默认小顶堆，取相反数使变成大顶堆
        
        ret = [-h[0][0]]
        for i in range(size, len(arr)):
            while h and h[0][1] <= i - size:  # 保证堆顶元素在窗口内
                heapq.heappop(h)
            heapq.heappush(h, (-arr[i], i))
            ret.append(-h[0][0])

        return ret

思路2：单调队列

• 使用一个严格单调队列 q 保存窗口内值的索引（保存索引，相当于保存了两个信息）；

• 这样每次将队首元素加入结果集即可；当队首元素不在窗口中时，出队；

Python

class Solution:
    def maxInWindows(self , arr: List[int], size: int) -> List[int]:
        # 窗口大于数组长度时
        if size > len(arr): return []
        
        from collections import deque
        
        # 初始化单调队列，严格单调
        q = deque()
        for i in range(size):
            # 当入队元素大于队尾时，队尾出队
            while q and arr[q[-1]] <= arr[i]:  # 这里用 <= 是避免相等时判断
                q.pop()
            q.append(i)  # 队列中保存 索引 而不是值，这样相当于保存了两个信息

        ret = [arr[q[0]]]  # 初始化结果序列
        for i in range(size, len(arr)):
            # 如果队首不在窗口内，则弹出（保存索引的好处）
            if q[0] == i - size:
                q.popleft()
            # 保持单调队列
            while q and arr[q[-1]] <= arr[i]:
                q.pop()
            q.append(i)
            ret.append(arr[q[0]])
        
        return ret