# Sliding Window Maximum

### 描述​

Given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Example 3:

Input: nums = [1,-1], k = 1
Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2
Output: [11]

Example 5:

Input: nums = [4,-2], k = 2
Output: [4]

Constraints:

• 1 <= nums.length <= $10^5$
• -$10^4$ <= nums[i] <= $10^4$
• 1 <= k <= nums.length

### 分析​

• 删除所有过期的索引
• 删除比当前元素小的所有元素，它们不可能是最大的。

### 代码​

#### 双端队列​

# Sliding Window Maximum# Using a Deque# Time Complexity: O(n), Space Complexity: O(k)from collections import dequeclass Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        result = []        q = deque()        for i in range(0, len(nums)):            if len(q)>0 and q[0] == i-k:                q.popleft()            while len(q) > 0 and nums[q[-1]] < nums[i]:                q.pop()            q.append(i)            if i >= k-1:                result.append(nums[q[0]])        return result

#### 动态规划​

# Sliding Window Maximum# Dynamic programming# Time Complexity: O(n), Space Complexity: O(n)class Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        n = len(nums)        if n * k == 0:            return []        # from left to right        left = [0] * n        left[0] = nums[0]        for i in range(1, n):            if i % k == 0: # block start                left[i] = nums[i]            else:                left[i] = max(left[i-1], nums[i])        # from right to left        right = [0] * n        right[n - 1] = nums[n - 1]        for i in reversed(range(n-1)):            if (i+1)%k == 0: # block end                right[i] = nums[i]            else:                right[i] = max(right[i + 1], nums[i])        return [max(left[i + k - 1], right[i]) for i in range(n - k + 1)]