مسئله · الگوریتم‌ها سخت JavaScript ·
Largest rectangle in a histogram
The list gives the heights of bars of width 1 standing side by side. Return the area of the largest rectangle that fits entirely under the bars. Up to 200,000 bars.
امضای تابع
/**
* @param {number[]} heights
* @returns {number}
*/
function largest_rectangle(heights)نمونه‌ها
largest_rectangle([2, 1, 5, 6, 2, 3]) // -> 10
largest_rectangle([2, 4]) // -> 4به‌همراه 6 تست مخفی و 2 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.
رتبه 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 · نحوه برگزاری راندها و امتیازدهی ←