給出一列數(shù)nums，求這列數(shù)從左到右長度k的滑動窗口內(nèi)的最大值依次是多少，維護(hù)一個優(yōu)先隊(duì)列，當(dāng)計(jì)算到第i個數(shù)時，優(yōu)先隊(duì)列里面保存所有長度k以內(nèi)值大于nums[i]的數(shù)的下標(biāo)（因此可以保證nums[0]是窗口長度k以內(nèi)的最大值）
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