滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

问题简述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值。

思路 1: 堆/优先队列

• 维护一个最大堆保存窗口内的值;

• 难点是如何保证堆内 (主要是堆顶) 的值正好在窗口内;

  • 方法是同时保存值的索引, 利用索引判断当前堆顶值是否在窗口内, 详见代码;

Python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        import heapq

        h = []
        for i in range(k):
            heapq.heappush(h, (-nums[i], i))
        
        ret = [-h[0][0]]
        for i in range(k, len(nums)):
            while h and h[0][1] <= i - k:
                heapq.heappop(h)
            heapq.heappush(h, (-nums[i], i))
            ret.append(-h[0][0])
        
        return ret

思路 2: 单调队列

滑动窗口最大值 (方法二) - 力扣官方题解