leetcode 239. 滑动窗口最大值

发表于 更新于 分类于 阅读次数：

解题思路

模拟窗口滑动，利用优先队列获取窗口内的最大值

注意：避免窗口外的数据造成影响

时间复杂度

O(nlogn)

空间复杂度

O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ret = []

        q = []
        for i, num in enumerate(nums):
            heapq.heappush(q, (-nums[i], i))
            if i < k-1:
                continue
            
            # 窗口外的元素要移除
            while q[0][1] <= i-k:
                heapq.heappop(q)
            
            ret.append(-q[0][0])

        return ret