编码母题 / P1 / 前端与专项架构 / 01

动态高度虚拟列表

先读清题意与边界，独立尝试，再展开思路并对照可运行的参考代码。

重要程度岗位专项难度困难预计完成50–70 分钟

难度按 LeetCode 简单／中等／困难三档估计；工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间，因经验而异。

题目是什么

动态高度列表支持测量后更新单项高度，并快速查询滚动位置对应的可见区间、偏移和总高度。不能每次查询都线性扫描全部项目。

输入输出示例

第 2 项高度变化后，其后所有项的起始偏移也应随之更新。

练习起手式与验证

复制代码后补全空方法，再运行下方三组验证；复杂题所需的辅助类型与输入准备一并放在代码块中。

/*
 * 题目：动态高度虚拟列表
 * 要求：动态高度列表支持测量后更新单项高度，并快速查询滚动位置对应的可见区间、偏移和总高度。
 * 不能每次查询都线性扫描全部项目。
 * 示例：第 2 项高度变化后，其后所有项的起始偏移也应随之更新。
 */
class FenwickTree {
  constructor(values) {}
  add(index, delta) {}
  update(index, value) {}
  prefix(count) {}
  countAtOrBefore(offset) {}
}
class VirtualListModel {
  constructor(count, estimatedHeight) {}
  updateHeight(index, height) {}
  getTotalHeight() {}
  getOffset(index) {}
  getRange(scrollTop, viewportHeight, overscan = 1) {}
}

const list = new VirtualListModel(5, 10);
console.log(list.getRange(12, 15, 0)); // 预期：{ start: 1, end: 2, offset: 10, totalHeight: 50, }
console.log(list.getRange(10, 20, 0)); // 预期：{ start: 1, end: 2, offset: 10, totalHeight: 50, }
list.updateHeight(0, 20);
console.log(list.getOffset(1)); // 预期：20

解题思路

展开思路、不变量与常见边界

关键切入点：Fenwick Tree 保存高度前缀和，支持 O(log n) 更新和按偏移定位。

核心模型：Fenwick Tree 保存高度前缀和，单点更新与前缀查询 O(log n)，通过二进制提升查找“前缀和不超过 offset 的最大项数”。overscan 只扩展索引范围，不改变可见性判断。总高度为全部前缀和。不变量：树中每项高度为正；offset(index) 等于前 index 项高度和；start 是包含 scrollTop 的项，end 覆盖 viewport 底部。生产组件还需滚动锚定和 ResizeObserver。

参考代码与验证

“关键机制”注释用于解释实现，下载链接提供未经页面注释修改的原始 JS 文件。

// 关键机制：Fenwick Tree 保存高度前缀和，支持 O(log n) 更新和按偏移定位。
class FenwickTree {
  constructor(values) {
    this.size = values.length;
    this.values = [...values];
    this.tree = Array(this.size + 1).fill(0);
    values.forEach((value, i) => this.add(i, value));
  }
  add(index, delta) {
    for (let i = index + 1; i <= this.size; i += i & -i) this.tree[i] += delta;
  }
  update(index, value) {
    if (!(value > 0)) throw new RangeError("height must be > 0");
    const delta = value - this.values[index];
    this.values[index] = value;
    this.add(index, delta);
  }
  prefix(count) {
    let sum = 0;
    for (let i = count; i > 0; i -= i & -i) sum += this.tree[i];
    return sum;
  }
  countAtOrBefore(offset) {
    let index = 0;
    let sum = 0;
    let bit = 1;
    while (bit << 1 <= this.size) bit <<= 1;
    for (; bit; bit >>= 1) {
      const next = index + bit;
      if (next <= this.size && sum + this.tree[next] <= offset) {
        index = next;
        sum += this.tree[next];
      }
    }
    return Math.min(index, this.size);
  }
}
class VirtualListModel {
  constructor(count, estimatedHeight) {
    if (!Number.isInteger(count) || count < 0 || !(estimatedHeight > 0))
      throw new RangeError("invalid list options");
    this.heights = new FenwickTree(Array(count).fill(estimatedHeight));
  }
  updateHeight(index, height) {
    if (!Number.isInteger(index) || index < 0 || index >= this.heights.size)
      throw new RangeError("invalid index");
    this.heights.update(index, height);
  }
  getTotalHeight() {
    return this.heights.prefix(this.heights.size);
  }
  getOffset(index) {
    return this.heights.prefix(index);
  }
  getRange(scrollTop, viewportHeight, overscan = 1) {
    if (!this.heights.size)
      return { start: 0, end: -1, offset: 0, totalHeight: 0 };
    const top = Math.max(0, scrollTop);
    const bottom = top + Math.max(0, viewportHeight);
    const visibleStart = Math.min(
      this.heights.countAtOrBefore(top),
      this.heights.size - 1,
    );
    let visibleEnd = this.heights.countAtOrBefore(bottom);
    if (visibleEnd > 0 && this.heights.prefix(visibleEnd) === bottom)
      visibleEnd -= 1;
    visibleEnd = Math.min(
      this.heights.size - 1,
      Math.max(visibleStart, visibleEnd),
    );
    const start = Math.max(0, visibleStart - overscan);
    const end = Math.min(this.heights.size - 1, visibleEnd + overscan);
    return {
      start,
      end,
      offset: this.getOffset(start),
      totalHeight: this.getTotalHeight(),
    };
  }
}

// 三组以上可直接运行的验证。
const list = new VirtualListModel(5, 10);
console.log(list.getRange(12, 15, 0)); // 预期：{ start: 1, end: 2, offset: 10, totalHeight: 50, }
console.log(list.getRange(10, 20, 0)); // 预期：{ start: 1, end: 2, offset: 10, totalHeight: 50, }
list.updateHeight(0, 20);
console.log(list.getOffset(1)); // 预期：20
console.log(list.getTotalHeight()); // 预期：60
console.log(new VirtualListModel(0, 10).getRange(0, 10)); // 预期：{ start: 0, end: -1, offset: 0, totalHeight: 0, }

复杂度分析

时间复杂度：构造 O(n log n)，更新／查询 O(log n)。构造逐项写 Fenwick Tree；前缀、更新和按偏移定位只走树高。

空间复杂度：O(n)。高度数组和 Fenwick Tree 各保存 n 项。

下载原始 JS 文件