8.Sliding Window Maximum

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;
    }
};

Time Complexity: O(n)