# 239. Sliding Window Maximum / Hard

You are 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]
Explanation:
Window position Max

[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

## Example 2:

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

## Comstraints

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

# Solution: Deque

## 思路

Deque 中的 front 必須是目前這個 window 中最大數字的 index，每次我們都要檢查新的數字是否大於 dq 最後的數字，也就是有機會成為 window 中最大數字的候選中，最小的那一個。如果新的數字比較大，就 pop back。動作持續到整個 Deque 呈現遞減數列為止。

## 效能

### Complexity

• Time Complexity: O(N)
• Space Complexity: O(N)

### LeetCode Result

• Runtime: 224 ms
• Memory Usage: 131.7 MB