原題
給出一個(gè)可能包含重復(fù)的整數(shù)數(shù)組惠遏，和一個(gè)大小為 k 的滑動(dòng)窗口, 從左到右在數(shù)組中滑動(dòng)這個(gè)窗口，找到數(shù)組中每個(gè)窗口內(nèi)的最大值淮逻。
給出數(shù)組 [1,2,7,7,8], 滑動(dòng)窗口大小為 k = 3. 返回 [7,7,8].
最開(kāi)始爽锥，窗口的狀態(tài)如下：
[1, 2 ,7 ,7 , 8], 最大值為 7;
然后窗口向右移動(dòng)一位：
[1, 2, 7, 7, 8], 最大值為 7;
最后窗口再向右移動(dòng)一位：
[1, 2, 7, 7, 8], 最大值為 8.
解題思路
- 方法一：最直觀的，每次從起點(diǎn)
i遍歷一遍窗口長(zhǎng)度j = i, i + k熏版，找最大值纷责，兩層for循環(huán)，時(shí)間復(fù)雜度O(n * k) - 方法二：維護(hù)一個(gè)hash heap撼短，每次移動(dòng)再膳，加入右邊元素O(logk)，減去左邊元素O(logk)曲横，返回maxheap中的最大值O(1)喂柒，時(shí)間復(fù)雜度為O(n * logk)
- 使用Deque，維護(hù)一個(gè)遞減的deque，時(shí)間復(fù)雜度為O(n)
已知 [1灾杰， 2蚊丐， 7， 3艳吠， 8吠撮， 5， 3讲竿， 2]
[1], 2進(jìn)入, 2 > 1 彈出1
[2], 7進(jìn)入泥兰， 7 > 2 彈出2
[7], 第一個(gè)窗口最大值為7，3進(jìn)入题禀，3 < 7
[7, 3], 第二個(gè)窗口最大值為7鞋诗，8進(jìn)入， 8 > 3 彈出3
[7], 8 > 7, 彈出7
[8], 第三個(gè)窗口最大值為8
為什么要用deque呢迈嘹？注意這種情況
當(dāng)前為[9, 8, 7], 6進(jìn)入削彬，6 < 7, 6進(jìn)入
[9, 8, 7, 6] 但是對(duì)K=3的窗口，必須要彈出9秀仲，這步就要用到deque
- Python中使用deque, 和list的API類似融痛，多了
popleft,appendleft,extendleft
import collections
d = collections.deque()
d.extend([1, 2, 3])
d.pop() # 3
d.popleft() # 1
d.append() # [2, 10]
d.appendleft() # [20, 2, 10]
d[0] # peek at leftmost item
d[-1] # peek at rightmost item
if d:
# d is not empty
else:
# d is empty
完整代碼
import collections
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
res = []
d = collections.deque()
for i in range(len(nums)):
while d and d[-1] < nums[i]:
d.pop()
d.append(nums[i])
if i > k - 1 and d[0] == nums[i - k]:
d.popleft()
if i >= k - 1:
res.append(d[0])
return res
