LeetCode 1146. 快照数组

2026-01-09 HGNULB 约 6 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 1146. 快照数组

题意分析

设计一个初始全为 0 的定长数组，支持三种操作：set 修改某个下标的当前值；snap 对整个数组「拍照存档」并返回本次存档的编号，编号从 0 开始依次递增；get 查询某个下标在指定存档时刻的值。

数组长度可以到五万，而三种操作的总调用次数也在五万量级。把这两个数字放在一起看就能读出关键信号：如果每次 snap 都复制一份完整数组，最坏情况下要复制五万次、每次五万个元素，无论时间还是空间都是二十五亿级，必然不可行。反过来注意到，set 的总次数也只有五万，也就是说整个生命周期内真正发生的修改是稀疏的——绝大多数下标在绝大多数快照里根本没变过。既然没变，就没必要为它们各存一份。

还有一处细节容易漏读：snap 返回的是本次存档的编号，之后编号才递增，所以第一次调用返回 0 而不是 1。另外允许在同一个快照区间内对同一下标多次 set，此时只有最后一次生效；也允许查询一个从未被修改过的下标，答案应当是初始值 0。

解法：按下标记录变更历史

核心思路

snap 时复制整个数组需要 $O(L)$ 时间和空间，但大多数位置在相邻快照之间没有变化。更合适的存储粒度是：每个下标只记录自己发生过的写入。

对每个下标维护按快照编号递增的记录列表 (snapId, value)，并放入哨兵 (0, 0)。维护两条不变量：

同一下标的记录按 snapId 严格递增；

列表中最后一条编号不超过目标快照的记录，就是该快照下的值。

同一快照周期内多次 set 时覆盖末条记录，而不是重复追加，从而维持编号严格递增。get 则在有序历史中二分查找最后一个 snapId <= target 的记录。

正确性来自“变更点”语义：某条记录从自己的快照编号开始生效，直到下一条记录出现；所以目标快照之前最近的一次写入恰好决定目标值。哨兵覆盖了“从未写入”的情况。

解题步骤

构造时为每个下标建立历史列表，并加入 (0, 0)。

set(index, val)：若末条记录编号等于当前 snapId，直接覆盖；否则追加新记录。

snap()：返回当前编号，再把编号加一。

get(index, id)：在该下标历史中二分寻找最后一个编号不大于 id 的位置，返回其值。

例如依次执行 set(0, 5)、snap()、set(0, 6)，下标 0 的历史为 [(0,5), (1,6)]。查询快照 0 时，最后一个编号不超过 0 的记录是 (0,5)，因此返回 5。

代码实现

import java.util.ArrayList;
import java.util.List;

class SnapshotArray {
    private final List<int[]>[] history;
    private int snapId;

    public SnapshotArray(int length) {
        history = new List[length];
        for (int i = 0; i < length; i++) {
            history[i] = new ArrayList<>();
            history[i].add(new int[]{0, 0});
        }
    }

    public void set(int index, int val) {
        List<int[]> records = history[index];
        int[] last = records.get(records.size() - 1);
        if (last[0] == snapId) {
            last[1] = val;
        } else {
            records.add(new int[]{snapId, val});
        }
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snap_id) {
        List<int[]> records = history[index];
        int left = 0;
        int right = records.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (records.get(mid)[0] <= snap_id) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return records.get(left)[1];
    }
}

type record struct {
    snapID int
    value  int
}

type SnapshotArray struct {
    history [][]record
    snapID  int
}

func Constructor(length int) SnapshotArray {
    history := make([][]record, length)
    for i := range history {
        history[i] = []record{{snapID: 0, value: 0}}
    }
    return SnapshotArray{history: history}
}

func (this *SnapshotArray) Set(index int, val int) {
    records := this.history[index]
    last := len(records) - 1
    if records[last].snapID == this.snapID {
        records[last].value = val
        return
    }
    this.history[index] = append(records, record{snapID: this.snapID, value: val})
}

func (this *SnapshotArray) Snap() int {
    id := this.snapID
    this.snapID++
    return id
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    records := this.history[index]
    left, right := 0, len(records)-1
    for left < right {
        mid := left + (right-left+1)/2
        if records[mid].snapID <= snap_id {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return records[left].value
}

复杂度分析

设数组长度为 $L$，某下标有 $m$ 条历史记录，所有 set 调用总数为 $q$。

时间复杂度：构造为 $O(L)$；set、snap 为 $O(1)$；get 为 $O(\log m)$。

空间复杂度：$O(L+q)$。每个下标一个哨兵，每次 set 最多新增一条记录。

关键点总结

快照数据稀疏变化时，保存变更记录比保存完整版本更合适。

get 的本质是对时间线做“前驱查询”：找最后一个不大于目标编号的版本。

同一快照内的重复写入必须覆盖，既节省空间，也保证版本编号唯一。

哨兵 (0, 0) 让未写入位置无需额外判空。

易错点总结

snap() 先自增再返回：所有快照编号整体错一位。

set 总是追加：同一版本产生重复编号，浪费空间并使边界二分更难保证。

get 查找第一个不小于目标的记录：会读到未来版本；应找最后一个不大于目标的记录。

忘记初始值 0：查询从未写过的下标会越界或无结果。

Go 中修改结构体副本而未写回切片：覆盖看似执行，历史值实际没有改变。

相似题目

题目	难度	考察点
307. 区域和检索 - 数组可修改	中等	支持单点修改与区间求和，靠树状数组而非版本
303. 区域和检索 - 数组不可变	简单	数据只读，预处理前缀和即可
729. 我的日程安排表 I	中等	在有序结构上二分找前驱后继以判断区间重叠
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分边界的纯练习，正是本题 `get` 的内核
146. LRU 缓存	中等	同为设计题，但约束是每个操作严格 $O(1)$