Untitled

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> dq;

        // fill the window first into the deque;
        for (int i = 0; i < k - 1; i++) {
            while (dq.size() && dq.back() < nums[i])
                dq.pop_back();
            dq.push_back(nums[i]);
        }

        vector<int> ans;
        for (int i = k - 1; i < n; i++) {
            while (dq.size() && dq.back() < nums[i])
                dq.pop_back();
            dq.push_back(nums[i]);
            ans.push_back(dq.front());
            if (nums[i - k + 1] == dq.front())
                dq.pop_front();
        }
        return ans;

        // Time O(N)
        // Space O(N)
    }
};