Sliding Window Maximum

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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

class Solution {

public:

    pair<int, int> findMax(vector<int>& nums, int st ,int end) {

        pair<int,int> ans = make_pair(INT_MIN, 0);

        // assuming k is always valid. i.e. less than nums.size().

        for (int i = st; i <= end; i++) {

            if (nums[i] > ans.first) {

                ans = make_pair(nums[i], i);

            }

        }

        return ans;

    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> ans;

        

        if (nums.size() == 0) {

            return ans;

        }

        

        int st = 0, end = k - 1;

        pair<int,int> first_max = findMax(nums, st, end);

        ans.push_back(first_max.first);

        for (int i = k; i < nums.size(); i++) {

            if (nums[i] > first_max.first) {

                first_max = make_pair(nums[i], i);

            } else if ((i - k) >= first_max.second) {

                first_max = findMax(nums, st + i - k + 1, end + i - k + 1);

            }

            ans.push_back(first_max.first);

        }

        return ans;

    }

};