239. Sliding window max

#include <stdlib.h>

int *maxSlidingWindow(int *nums, int numsSize, int k, int *returnSize) {
    int *maxs = malloc(sizeof(int) * (numsSize - k + 1));
    int *dq = malloc(sizeof(int) * numsSize); // indices, values decreasing
    int head = 0, tail = 0;
    *returnSize = 0;

    // i is the right pointer
    // i - k + 1 is the left pointer
    for (int i = 0; i < numsSize; i++) {
        if (head < tail && dq[head] < i - k + 1)
            head++;

        while (head < tail && nums[i] > nums[dq[tail - 1]])
            tail--;
        dq[tail++] = i;

        if (i >= k - 1)
            maxs[(*returnSize)++] = nums[dq[head]];
    }

    free(dq);
    return maxs;
}

#include <deque>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    vector<int> maxs;
    deque<int> dq;

    // i is the right pointer
    // i - k + 1 is the left pointer
    for (int i = 0; i < nums.size(); i++) {
      if (!dq.empty() && dq.front() < i - k + 1) {
        dq.pop_front();
      }

      while (!dq.empty() && nums[i] > nums[dq.back()])
        dq.pop_back();
      dq.push_back(i);

      if (i >= k - 1)
        maxs.push_back(nums[dq.front()]);
    }

    return maxs;
  }
};

package main

func maxSlidingWindow(nums []int, k int) []int {
    maxs := []int{}
    dq := []int{} // indices, values decreasing

    // i is the right pointer
    // i - k + 1 is the left pointer
    for i, n := range nums {
        if len(dq) > 0 && dq[0] < i-k+1 {
            dq = dq[1:]
        }

        for len(dq) > 0 && n > nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)

        if i >= k-1 {
            maxs = append(maxs, nums[dq[0]])
        }
    }

    return maxs
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxs = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing

        // i is the right pointer
        // i - k + 1 is the left pointer
        for (int i = 0; i < nums.length; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
                dq.pollFirst();

            while (!dq.isEmpty() && nums[i] > nums[dq.peekLast()])
                dq.pollLast();
            dq.offerLast(i);

            if (i >= k - 1)
                maxs[i - k + 1] = nums[dq.peekFirst()];
        }

        return maxs;
    }
}

class Solution {
  maxSlidingWindow(nums, k) {
    const maxs = [];
    const dq = []; // indices, values decreasing
    let head = 0;

    // i is the right pointer
    // i - k + 1 is the left pointer
    for (let i = 0; i < nums.length; i++) {
      if (head < dq.length && dq[head] < i - k + 1) head++;

      while (head < dq.length && nums[i] > nums[dq[dq.length - 1]]) dq.pop();
      dq.push(i);

      if (i >= k - 1) maxs.push(nums[dq[head]]);
    }

    return maxs;
  }
}

from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        maxs = []
        dq = deque()  # indices, values decreasing

        # i is the right pointer
        # i - k + 1 is the left pointer
        for i, n in enumerate(nums):
            if dq and dq[0] < i - k + 1:
                dq.popleft()

            while dq and n > nums[dq[-1]]:
                dq.pop()
            dq.append(i)

            if i >= k - 1:
                maxs.append(nums[dq[0]])

        return maxs

use std::collections::VecDeque;

struct Solution;

impl Solution {
    fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut maxs = Vec::new();
        let mut dq: VecDeque<usize> = VecDeque::new(); // indices, values decreasing

        // i is the right pointer
        // i + 1 - k is the left pointer
        for i in 0..nums.len() {
            if dq.front().is_some_and(|&f| f + k <= i) {
                dq.pop_front();
            }

            while dq.back().is_some_and(|&b| nums[i] > nums[b]) {
                dq.pop_back();
            }
            dq.push_back(i);

            if i + 1 >= k {
                maxs.push(nums[dq[0]]);
            }
        }

        maxs
    }
}