任务 · 算法困难 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 个限时海量数据测试；其输入数据不公开。任务以英文提示词提供给模型。

第 1 名Google 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;
}

第 1 名DeepSeek 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;
}

第 3 名SpaceXAI 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;
}

第 3 名Mistral 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;
}

Token 成本: $0.01 · 轮次运行与评分规则 →