โจทย์ · อัลกอริทึม ยาก JavaScript ·

Largest rectangle in a histogram

/**
 * @param {number[]} heights
 * @returns {number}
 */
function largest_rectangle(heights)

largest_rectangle([2, 1, 5, 6, 2, 3])  // -> 10
largest_rectangle([2, 4])  // -> 4

• อันดับ #1Google Gemini 4 Argonแก้ผ่าน · ผ่าน 10 จาก 10 การทดสอบตอบใน 6.8 วินาที · เวลาประมวลผล 121 มิลลิวินาที · $0.0032

  ✓	largest_rectangle([2, 1, 5, 6, 2, 3])ค่าที่คาดหวัง 10	7 มิลลิวินาที
  ✓	largest_rectangle([2, 4])ค่าที่คาดหวัง 4	2 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 3 มิลลิวินาที✓ 3 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 51 มิลลิวินาที⏱ 52 มิลลิวินาที
  โค้ด

  /**
   * @param {number[]} heights
   * @returns {number}
   */
  function largest_rectangle(heights) {
      const n = heights.length;
      if (n === 0) return 0;
  
      // Using Int32Array for the stack avoids dynamic array allocations and is very fast
      const stack = new Int32Array(n + 1);
      let top = -1;
      let maxArea = 0;
  
      for (let i = 0; i <= n; i++) {
          const h = i === n ? 0 : heights[i];
          while (top >= 0 && heights[stack[top]] >= h) {
              const height = heights[stack[top--]];
              const width = top === -1 ? i : i - stack[top] - 1;
              const area = height * width;
              if (area > maxArea) {
                  maxArea = area;
              }
          }
          stack[++top] = i;
      }
  
      return maxArea;
  }

• อันดับ #1DeepSeek V4.1 Flashแก้ผ่าน · ผ่าน 10 จาก 10 การทดสอบตอบใน 2.4 วินาที · เวลาประมวลผล 128 มิลลิวินาที · $0.0001

  ✓	largest_rectangle([2, 1, 5, 6, 2, 3])ค่าที่คาดหวัง 10	2 มิลลิวินาที
  ✓	largest_rectangle([2, 4])ค่าที่คาดหวัง 4	2 มิลลิวินาที

  ✓ 1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 22 มิลลิวินาที✓ 3 มิลลิวินาที✓ 4 มิลลิวินาที⏱ 26 มิลลิวินาที⏱ 67 มิลลิวินาที
  โค้ด

  function largest_rectangle(heights) {
    const n = heights.length;
    if (n === 0) return 0;
    const stack = new Int32Array(n + 1);
    let top = -1;
    let best = 0;
    for (let i = 0; i <= n; i++) {
      const h = i < n ? heights[i] : 0;
      while (top >= 0 && heights[stack[top]] >= h) {
        const height = heights[stack[top--]];
        const left = top >= 0 ? stack[top] : -1;
        const area = height * (i - left - 1);
        if (area > best) best = area;
      }
      stack[++top] = i;
    }
    return best;
  }

• อันดับ #3SpaceXAI Grok 4.7แก้ผ่าน · ผ่าน 10 จาก 10 การทดสอบตอบใน 16 วินาที · เวลาประมวลผล 190 มิลลิวินาที · $0.0099

  ✓	largest_rectangle([2, 1, 5, 6, 2, 3])ค่าที่คาดหวัง 10	2 มิลลิวินาที
  ✓	largest_rectangle([2, 4])ค่าที่คาดหวัง 4	3 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ 18 มิลลิวินาที✓ 1 มิลลิวินาที✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที⏱ 44 มิลลิวินาที⏱ 118 มิลลิวินาที
  โค้ด

  function largest_rectangle(heights) {
      const n = heights.length;
      const stack = [];
      let maxArea = 0;
      for (let i = 0; i <= n; i++) {
          const h = i === n ? 0 : heights[i];
          while (stack.length > 0 && heights[stack[stack.length - 1]] > h) {
              const height = heights[stack.pop()];
              const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
              const area = height * width;
              if (area > maxArea) maxArea = area;
          }
          stack.push(i);
      }
      return maxArea;
  }

• อันดับ #3Mistral Devstral 2 2512แก้ผ่าน · ผ่าน 10 จาก 10 การทดสอบตอบใน 1.4 วินาที · เวลาประมวลผล 200 มิลลิวินาที · $0.0004

  ✓	largest_rectangle([2, 1, 5, 6, 2, 3])ค่าที่คาดหวัง 10	3 มิลลิวินาที
  ✓	largest_rectangle([2, 4])ค่าที่คาดหวัง 4	1 มิลลิวินาที

  ✓ 3 มิลลิวินาที✓ 5 มิลลิวินาที✓ 1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที⏱ 68 มิลลิวินาที⏱ 117 มิลลิวินาที
  โค้ด

  function largest_rectangle(heights) {
      const stack = [];
      let maxArea = 0;
      const n = heights.length;
  
      for (let i = 0; i <= n; i++) {
          const h = i === n ? 0 : heights[i];
          while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
              const height = heights[stack.pop()];
              const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
              maxArea = Math.max(maxArea, height * width);
          }
          stack.push(i);
      }
  
      return maxArea;
  }

ค่าใช้จ่ายโทเค็น: $0.01 · วิธีจัดการแข่งขันและการคิดคะแนน →