Sliding Window Maximum

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        ans.reserve(nums.size() - k + 1);
        for (int i = 0; i < (int)nums.size(); ++i) {
            while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
            dq.push_back(i);
            if (dq.front() <= i - k) dq.pop_front();
            if (i >= k - 1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

func maxSlidingWindow(nums []int, k int) []int {
    dq := []int{}
    ans := make([]int, 0, len(nums)-k+1)
    for i := 0; i < len(nums); i++ {
        for len(dq) > 0 && nums[dq[len(dq)-1]] <= nums[i] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        if dq[0] <= i-k {
            dq = dq[1:]
        }
        if i >= k-1 {
            ans = append(ans, nums[dq[0]])
        }
    }
    return ans
}

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq: deque[int] = deque()
        ans: List[int] = []
        for i, x in enumerate(nums):
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                ans.append(nums[dq[0]])
        return ans

function maxSlidingWindow(nums, k) {
    const dq = [];
    let head = 0;
    const ans = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
        dq.push(i);
        if (dq[head] <= i - k) head++;
        if (i >= k - 1) ans.push(nums[dq[head]]);
    }
    return ans;
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int idx = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();
            if (i >= k - 1) ans[idx++] = nums[dq.peekFirst()];
        }
        return ans;
    }
}

function maxSlidingWindow(nums: number[], k: number): number[] {
    const dq: number[] = [];
    let head = 0;
    const ans: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
        dq.push(i);
        if (dq[head] <= i - k) head++;
        if (i >= k - 1) ans.push(nums[dq[head]]);
    }
    return ans;
}