Posted on 2023-08-16 16:53
Uriel 閱讀(64)
評論(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