pg

Given an array 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:

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


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

// we can use deque to solve this problem
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> dq;
for(int i = 0; i < nums.size(); i++){

// if the current right side of window is i and the current left side of window is dq.front()
// then if the size of the window is larger than k, we move the left side by pop element from the front of the deque

while(!dq.empty() && dq.front() < i-k+1){
dq.pop_front();
}

// the dq needs to contain the largest numbers of every subarray
// so the method is when we need to compare the number in the deque and the nums[i], if the number is smaller than nums[i], then we pop the number, if not we keep it in the deque. So if the nums[i] is the largest in a subarray, some numbers which are before it and smaller than it will be popped, some numbers which are after it and also smaller than it will not be pushed into the dq.

while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if(i >= k-1)
res.push_back(nums[dq.front()]);
}
return res;
}