Đề bài · thuật toán khó 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.5đã giải · 10/10 testtrả lời trong 6.4 giây · thời gian chạy 679 ms · $0.01

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)kỳ vọng [3, 3, 5, 5, 6, 7]	1 ms
  ✓	window_max([1], 1)kỳ vọng [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 Flashđã giải · 10/10 testtrả lời trong 755 ms · thời gian chạy 717 ms · $0.0001

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)kỳ vọng [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)kỳ vọng [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 Terrađã giải · 10/10 testtrả lời trong 3.0 giây · thời gian chạy 754 ms · $0.0011

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)kỳ vọng [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)kỳ vọng [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 Nextchưa giải được · 9/10 testtrả lời trong 3.4 giây · thời gian chạy 956 ms · $0.0002

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)kỳ vọng [3, 3, 5, 5, 6, 7]	4 ms
  ✓	window_max([1], 1)kỳ vọng [1]	4 ms

  ✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ 440 ms⏱ quá giới hạn thời gian
  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;
  }

  Lần thử thứ hai

  chưa giải được · 9/10 testtrả lời trong 3.0 giây · $0.0003

  Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.

  ✓	window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)kỳ vọng [3, 3, 5, 5, 6, 7]	2 ms
  ✓	window_max([1], 1)kỳ vọng [1]	3 ms

  ✓ <1 ms✓ 4 ms✓ 2 ms✓ 17 ms✓ 2 ms✓ <1 ms⏱ 468 ms⏱ quá giới hạn thời gian

  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;
  }

Chi phí token: $0.01 · Cách thức thi đấu và tính điểm →