# LeetCode: 239. 滑动窗口最大值¶

## 1、题目描述¶

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

滑动窗口的位置                最大值

------

[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7



• 你能在线性时间复杂度内解决此题吗？

## 2、解题思路¶

• 滑动窗口法

• 使用堆维持窗口最大值

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
import heapq
N = len(nums)
res = []

pos = 1
window = [-x for x in nums[:k]]
heapq.heapify(window)
res.append(-window[0])
while pos < N - k + 1:
window.remove(-nums[pos-1])
heapq.heapify(window)
heapq.heappush(window, -nums[pos + k - 1])
res.append(-window[0])
pos += 1

return res

• 双向队列法

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
from collections import deque
if not nums:
return []

windows = deque(maxlen=k)

def process_deque(deq: deque, pos: int):
if deq and deq[0] + k == pos:
deq.popleft()
while deq and nums[deq[-1]] < nums[pos]:
deq.pop()
deq.append(pos)

for i in range(k - 1):
process_deque(windows, i)
res = []
for i in range(k - 1, len(nums)):
process_deque(windows, i)
res.append(nums[windows[0]])
return res