Posted on 2023-08-16 16:53
Uriel 阅读(31)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code 、
游标.移动窗口
给出一列数nums，求这列数从左到右长度k的滑动窗口内的最大值依次是多少，维护一个优先队列，当计算到第i个数时，优先队列里面保存所有长度k以内值大于nums[i]的数的下标（因此可以保证nums[0]是窗口长度k以内的最大值）
1 #239
2 #Runtime: 1773 ms (Beats 16%)
3 #Memory: 30.5 MB (Beats 48.38%)
4
5 class Solution(object):
6 def maxSlidingWindow(self, nums, k):
7 """
8 :type nums: List[int]
9 :type k: int
10 :rtype: List[int]
11 """
12 wd_max = []
13 ans = []
14 for i in range(len(nums)):
15 if wd_max and wd_max[0] == i - k:
16 wd_max.pop(0)
17 while wd_max and nums[wd_max[-1]] < nums[i]:
18 wd_max.pop()
19 wd_max.append(i)
20 if i >= k - 1:
21 ans.append(nums[wd_max[0]])
22 return ans