Window + Monotonic Deque (Sliding Window Sub-pattern)

// Maximum of every window of size k using a monotonic deque.
// dq holds indices; their values are in decreasing order front -> back.
vector<int> windowMax(vector<int>& a, int k) {
    deque<int> dq;
    vector<int> res;
    for (int right = 0; right < (int)a.size(); right++) {
        while (!dq.empty() && a[dq.back()] <= a[right]) dq.pop_back(); // can never be max again
        dq.push_back(right);
        if (dq.front() <= right - k) dq.pop_front();                 // fell out of the window
        if (right >= k - 1) res.push_back(a[dq.front()]);            // front = current max
    }
    return res;
}