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 of size K
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 One can solve this problem by Brute Force method by running two loops and find the maximum in each sliding window of size k, but that will be O(n*n). We need to optimize it further for that we can use Deque which will be Monotonic(Decreasing) in nature such that it always has front element as maximum element and also we will only store the index in the deque so that we can access the element directly to check. Below is the code implementation
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i=0; i<nums.size(); i++)
{
//Check if the maximum element is at first position in the sliding window, pop it from deque to get next maximum in next sliding window
if (!dq.empty() && dq.front() == i-k)
dq.pop_front();
//This loop is to ensure the deque is in decreasing order
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;
}
};I hope you understands the algorithm and solution. If you still has doubt .Pleas leave a comment.