**source:**https://leetcode.com/problems/sliding-window-maximum**C/C++**

**Solution to LeetCode**problem

**239**.

**Sliding Window Maximum**.

## Problem

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*.

## Examples

**Example 1:**

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

Output:[3,3,5,5,6,7]

Explanation:

1 2 3 4 5 6 7 8 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]

## Constraints

`1 <= nums.length <= 10`

^{5}`-10`

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

## Solution

Two solutions:

**Fast**. Using deque.**We will track the index of the max value for each window**. - Iterate through the numbers- If the first element (index) is outside the window, then we remove it (
`pop_front`

) - We remove all the indexes that have nums
`<`

thant the one at the current index. - We add the new index to the window/deque (
`push_back`

). - Once the index is corresponds to the last element of the window
- We can add the num at the index of first element (
`front`

) of the deque to the results, as it holds the max value for the window.

- We can add the num at the index of first element (

- If the first element (index) is outside the window, then we remove it (
**Slow**. Using multiset (using the`greater`

function object) to sort the elements from greater to lower. - Iterate through the numbers.- We add the number to the window.
- Once the multiset has the size of the window we take the first element, as it will be the greater one in the window.
- We remove the element that corresponds to the first element of the window.

### Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

### Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
multiset<int> w;
int i = 0;
for (i=0; i<k-1; i+=1)
w.insert(nums[i]);
while (i<nums.size()) {
w.insert(nums[i]);
auto n = w.rbegin();
result.push_back(*n);
w.erase(w.lower_bound(nums[i-k+1]));
i += 1;
}
return result;
}
};