## Problem

**Problem ID**: 239

**Title**: Sliding Window Maximum

**Difficulty**: Hard

**Description**:

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 = 3Output:[3,3,5,5,6,7]Explanation:Window position Max --------------- ----- [1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7

**Example 2:**

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

**Constraints:**

`1 <= nums.length <= 10`

^{5}`-10`

^{4}<= nums[i] <= 10^{4}`1 <= k <= nums.length`

## Thoughts

Finding the O(N) solution to this question is quite hard and it was obvious that there is a O(N) solution.

## Solution

**General Idea**

To solve this problem you will need to make the following key observations:

- When adding number at index
`i`

into the sliding window, any number,`j`

, with index`j < i`

and smaller than the new number`nums[j] < nums[i]`

will never be the maximum number for the window.- The reason for this is that all subsequent window that has
`j`

will also have`i`

and`nums[i]`

will be the maximum number

- The reason for this is that all subsequent window that has

Intuition:

- Carry out normal sliding window where we iterate through each element and add it to the queue. If the queue size is bigger than the window size pop from the front of the queue.
- Instead of having a FIFO queue, the queue will represent all the possible largest
element for now and all other future iteration.
- This is constructed by poping from the back of the queue if the back element is smaller than the current element. Represent a previous candidate being replaced by the current element.

### Implementation

```
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> d;
vector<int> ret;
for (auto i = size_t{0}; i < nums.size(); i++) {
while (!d.empty() && i - d.front() >= k) d.pop_front();
while (!d.empty() && nums[d.back()] < nums[i]) d.pop_back();
d.push_back(i);
if (i >= k -1) ret.push_back(nums[d.front()]);
}
return ret;
}
};
```