Défi · algorithmes difficile JavaScript ·

Sliding window maximum

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number[]}
 */
function window_max(nums, k)

window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)  // -> [3, 3, 5, 5, 6, 7]
window_max([1], 1)  // -> [1]

• #1Anthropic Claude Opus 5.5résolu · 10 sur 10 testsréponse en 6.4 s · exécution 679 ms · $0.01

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)attendu [3, 3, 5, 5, 6, 7]	1 ms
  ✓	window_max([1], 1)attendu [1]	1 ms

  ✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 401 ms⏱ 270 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const m = n - k + 1;
    const res = new Array(m);
    const dq = new Int32Array(n);
    let h = 0, t = 0;
    for (let i = 0; i < n; i++) {
      const v = nums[i];
      // Remove indices whose values can no longer be a window maximum.
      while (t > h && nums[dq[t - 1]] <= v) t--;
      dq[t++] = i;
      // Drop the front index once it leaves the window.
      if (dq[h] <= i - k) h++;
      if (i >= k - 1) res[i - k + 1] = nums[dq[h]];
    }
    return res;
  }

• #1DeepSeek V4.1 Flashrésolu · 10 sur 10 testsréponse en 755 ms · exécution 717 ms · $0.0001

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)attendu [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)attendu [1]	1 ms

  ✓ 3 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ 1 ms✓ 1 ms⏱ 396 ms⏱ 306 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const res = new Array(n - k + 1);
    const dq = new Int32Array(n); // indices, monotonic decreasing by value
    let head = 0, tail = 0, ri = 0;
    for (let i = 0; i < n; i++) {
      const v = nums[i];
      // pop smaller/equal from back
      while (tail > head && nums[dq[tail - 1]] <= v) tail--;
      dq[tail++] = i;
      // remove out-of-window from front
      if (dq[head] <= i - k) head++;
      if (i >= k - 1) res[ri++] = nums[dq[head]];
    }
    return res;
  }

• #1OpenAI GPT-6.1 Terrarésolu · 10 sur 10 testsréponse en 3.0 s · exécution 754 ms · $0.0011

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)attendu [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)attendu [1]	1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 3 ms✓ 3 ms⏱ 411 ms⏱ 332 ms
  Code

  function window_max(nums, k) {
    const n = nums.length;
    const result = new Array(n - k + 1);
    const deque = new Int32Array(n);
    let head = 0;
    let tail = 0;
  
    for (let i = 0; i < n; i++) {
      while (head < tail && deque[head] <= i - k) head++;
      while (head < tail && nums[deque[tail - 1]] <= nums[i]) tail--;
      deque[tail++] = i;
  
      if (i >= k - 1) result[i - k + 1] = nums[deque[head]];
    }
  
    return result;
  }

• #4Qwen3 Coder Nextnon résolu · 9 sur 10 testsréponse en 3.4 s · exécution 956 ms · $0.0002

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)attendu [3, 3, 5, 5, 6, 7]	4 ms
  ✓	window_max([1], 1)attendu [1]	4 ms

  ✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ 440 ms⏱ délai limite dépassé
  Code

  /**
   * @param {number[]} nums
   * @param {number} k
   * @returns {number[]}
   */
  function window_max(nums, k) {
      if (nums.length === 0 || k <= 0) return [];
      if (k > nums.length) k = nums.length;
      
      const result = [];
      const deque = []; // stores indices of elements in decreasing order
      
      for (let i = 0; i < nums.length; i++) {
          // Remove indices that are out of the current window
          while (deque.length > 0 && deque[0] <= i - k) {
              deque.shift();
          }
          
          // Remove indices whose corresponding values are less than current element
          // This maintains decreasing order in the deque
          while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
              deque.pop();
          }
          
          // Add current index to deque
          deque.push(i);
          
          // If we have processed at least k elements, add maximum to result
          if (i >= k - 1) {
              result.push(nums[deque[0]]);
          }
      }
      
      return result;
  }

  Second essai

  non résolu · 9 sur 10 testsréponse en 3.0 s · $0.0003

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)attendu [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)attendu [1]	3 ms

  ✓ <1 ms✓ 4 ms✓ 2 ms✓ 17 ms✓ 2 ms✓ <1 ms⏱ 468 ms⏱ délai limite dépassé

  Code

  /**
   * @param {number[]} nums
   * @param {number} k
   * @returns {number[]}
   */
  function window_max(nums, k) {
      if (nums.length === 0 || k <= 0) return [];
      if (k > nums.length) k = nums.length;
      
      const result = [];
      const deque = []; // stores indices of elements in decreasing order
      
      for (let i = 0; i < nums.length; i++) {
          // Remove indices that are out of the current window
          while (deque.length > 0 && deque[0] <= i - k) {
              deque.shift();
          }
          
          // Remove indices whose corresponding values are less than current element
          while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
              deque.pop();
          }
          
          deque.push(i);
          
          if (i >= k - 1) {
              result.push(nums[deque[0]]);
          }
      }
      
      return result;
  }

Coût en jetons: $0.01 · Déroulement et calcul des scores →