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]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Example 5:
Input: nums = [4,-2], k = 2
Output: [4]
Solution : (Normal Sliding Window)
class Solution
{
public:
int findMax(vector<int> v, int start, int end)
{
int mx = INT_MIN;
for (int i = start; i < end; i++)
{
if (v[i] > mx)
{
mx = v[i];
}
}
return mx;
}
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
vector<int> v;
int mx = findMax(nums, 0, k);
for (int i = 0; i <= nums.size() - k; i++)
{
v.push_back(mx);
if (i + k < nums.size())
{
if (nums[i + k] > mx)
{
mx = nums[i + k];
}
if (nums[i] == mx)
{
mx = findMax(nums, i + 1, i + 1 + k);
}
}
}
return v;
}
};
Time Complexity: O(nk)
Solution II: (Using deque)
class Solution
{
public:
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
vector<int> v;
deque<int> q;
for (int i = 0; i < k; i++)
{
while (!q.empty() && nums[i] >= nums[q.back()])
{
q.pop_back();
}
q.push_back(i);
}
for (int i = 0; i <= nums.size() - k; i++)
{
v.push_back(nums[q.front()]);
while (!q.empty() && q.front() <= i)
{
q.pop_front();
}
if (i + k < nums.size())
{
while (!q.empty() && nums[i + k] >= nums[q.back()])
{
q.pop_back();
}
q.push_back(i + k);
}
}
return v;
}
};