// ─── Deque backed by doubly linked list ──────────────────────
class DequeNode {
  constructor(value) { this.value = value; this.prev = null; this.next = null; }
}

class Deque {
  #head = null;
  #tail = null;
  #size = 0;

  pushFront(value) {
    const node = new DequeNode(value);
    if (!this.#head) { this.#head = this.#tail = node; }
    else { node.next = this.#head; this.#head.prev = node; this.#head = node; }
    this.#size++;
  }

  pushBack(value) {
    const node = new DequeNode(value);
    if (!this.#tail) { this.#head = this.#tail = node; }
    else { node.prev = this.#tail; this.#tail.next = node; this.#tail = node; }
    this.#size++;
  }

  popFront() {
    if (!this.#head) return null;
    const val = this.#head.value;
    this.#head = this.#head.next;
    if (this.#head) this.#head.prev = null; else this.#tail = null;
    this.#size--;
    return val;
  }

  popBack() {
    if (!this.#tail) return null;
    const val = this.#tail.value;
    this.#tail = this.#tail.prev;
    if (this.#tail) this.#tail.next = null; else this.#head = null;
    this.#size--;
    return val;
  }

  peekFront() { return this.#head?.value ?? null; }
  peekBack()  { return this.#tail?.value ?? null; }
  isEmpty()   { return this.#size === 0; }
  get size()  { return this.#size; }
}

// ─── Monotonic Deque: Sliding Window Maximum in O(n) ─────────
// ❌ Naive O(n²): for each window, scan k elements for max
// ✅ Monotonic deque O(n): maintain decreasing deque of indices
function slidingWindowMax(nums, k) {
  const dq = new Deque(); // Stores indices, front = current max index
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    while (!dq.isEmpty() && dq.peekFront() < i - k + 1) dq.popFront();

    // Remove indices whose values are smaller than current (they can never be max)
    while (!dq.isEmpty() && nums[dq.peekBack()] < nums[i]) dq.popBack();

    dq.pushBack(i);

    if (i >= k - 1) result.push(nums[dq.peekFront()]); // Front is always max
  }
  return result;
}

console.log(slidingWindowMax([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]