Tugas · algoritma sulit 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.5selesai · 10 dari 10 pengujianrespons dalam 6.4 dtk · waktu eksekusi 679 md · $0.01

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)diharapkan [3, 3, 5, 5, 6, 7]	1 md
  ✓	window_max([1], 1)diharapkan [1]	1 md

  ✓ <1 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 401 md⏱ 270 md
  Kode

  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 Flashselesai · 10 dari 10 pengujianrespons dalam 755 md · waktu eksekusi 717 md · $0.0001

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)diharapkan [3, 3, 5, 5, 6, 7]	2 md
  ✓	window_max([1], 1)diharapkan [1]	1 md

  ✓ 3 md✓ 1 md✓ 2 md✓ 3 md✓ 1 md✓ 1 md⏱ 396 md⏱ 306 md
  Kode

  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 Terraselesai · 10 dari 10 pengujianrespons dalam 3.0 dtk · waktu eksekusi 754 md · $0.0011

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)diharapkan [3, 3, 5, 5, 6, 7]	2 md
  ✓	window_max([1], 1)diharapkan [1]	1 md

  ✓ <1 md✓ 1 md✓ 1 md✓ <1 md✓ 3 md✓ 3 md⏱ 411 md⏱ 332 md
  Kode

  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 Nexttidak selesai · 9 dari 10 pengujianrespons dalam 3.4 dtk · waktu eksekusi 956 md · $0.0002

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)diharapkan [3, 3, 5, 5, 6, 7]	4 md
  ✓	window_max([1], 1)diharapkan [1]	4 md

  ✓ <1 md✓ 1 md✓ 3 md✓ 2 md✓ <1 md✓ 1 md⏱ 440 md⏱ batas waktu terlampaui
  Kode

  /**
   * @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;
  }

  Percobaan kedua

  tidak selesai · 9 dari 10 pengujianrespons dalam 3.0 dtk · $0.0003

  Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)diharapkan [3, 3, 5, 5, 6, 7]	2 md
  ✓	window_max([1], 1)diharapkan [1]	3 md

  ✓ <1 md✓ 4 md✓ 2 md✓ 17 md✓ 2 md✓ <1 md⏱ 468 md⏱ batas waktu terlampaui

  Kode

  /**
   * @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;
  }

Biaya token: $0.01 · Cara babak dijalankan dan dinilai →