LeetCode 1146. 快照数组
题目描述
题意分析
维护一个初值全为零的定长数组。
set(index, val)修改当前值；snap()保存当前状态并返回编号，编号从零开始；get(index, snap_id)返回指定历史快照中该下标的值。创建快照后的新写入不能改变旧快照。同一次快照之前，对同一位置写多次只以最后一次为准；没有写入的位置继续沿用原值。题目保证查询的快照编号已经由
snap()创建。
解法：按下标记录变更历史
核心思路
[!blue]
每次快照都复制整条数组，会把未变化的位置也重复保存。实际上一个位置的值只在写入时改变，可以让每个下标单独保存按版本递增的记录
(版本号, 值)，快照只负责划分写入属于哪个版本。
snapId表示当前尚未完成的快照周期。set发现末条记录也属于这个周期，就覆盖末条值，因为周期内的中间写入不会被历史查询单独观察；若末条属于更早的周期，就追加新记录，保证已经完成的快照内容不再改写。snap()返回当前编号后再递增，后续写入自然进入新周期。一条记录从它的版本开始生效，直到下一条记录出现。查询版本
t时，需要最后一条编号不大于t的记录，而不是必须找到恰好等于t的记录：期间即使创建了多个快照，只要这个位置没写入，旧值就一直有效。记录编号有序，可以二分最后一个满足
版本 <= t的位置。可行时保留中点并向右找，不可行时排除中点和右侧。因为更新使用left = mid，中点向上取整，才能在只剩两个候选时继续收缩。每个下标预置记录
(0, 0)，保证所有合法历史查询至少有一个可用初值。首次快照之前的写入允许覆盖这条记录；首次快照完成后，版本号已经推进，旧记录就不会再被改动。
解题步骤
- 构造时创建各位置的历史列表，分别放入
(0, 0)，当前版本从零开始。- 写入时比较最后一条记录的版本：等于当前版本则覆盖值，否则追加
(当前版本, 新值)。- 创建快照时，先返回当前版本号，再将当前版本加一，不复制任何数组内容。
- 查询时取得对应位置的历史，在闭区间内用上中点二分最后一个版本不晚于目标的记录。
- 两端相遇后返回该记录的值；未来周期的记录会在二分中被排除。
代码实现
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) {
// 条件成立时令 left=mid 保留当前中点，向上取整保证两个候选时仍能收缩
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 {
// 条件成立时令 left=mid 保留当前中点，向上取整保证两个候选时仍能收缩
mid := left + (right-left+1)/2
if records[mid].snapID <= snap_id {
left = mid
} else {
right = mid - 1
}
}
return records[left].value
}
复杂度分析
- 时间复杂度：数组长度为
L时构造为 $O(L)$；写入均摊 $O(1)$，创建快照为 $O(1)$；某下标有m条记录时，查询为 $O(\log(m+1))$。- 空间复杂度：$O(L+q)$，
q为累计写入次数。每个位置有一条初值记录，每次写入最多追加一条，同周期覆盖不会增加记录数。
关键点总结
[!green]
- 按位置保存变更，快照只是版本分界，无需复制没有改变的数据。
- 当前周期允许覆盖，已完成版本只能保留，才能保证历史值稳定。
- 查询取最后一个不晚于目标的版本，自动跨越没有写入的快照空档。
- 保留可行中点向右搜索时使用上中点，保证区间收缩。
易错点总结
[!yellow]
- 创建快照先增加编号再返回，第一次编号会变成一，与接口约定不一致。
- 后续写入直接覆盖历史最后值，却不检查版本，已经保存的快照会被篡改。
- 只找与目标完全相等的记录，漏掉这个版本未写入、但沿用更早值的情况。
- 找第一个不小于目标的记录，可能返回查询时尚未生效的未来值。
- 二分用下中点同时执行
left = mid，两个候选时可能原地循环。- Go 追加历史后不把新切片写回
history[index]，新长度或重新分配的底层数组不会保存到对象中。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 981. 基于时间的键值存储 | 中等 | 同样为每个键或下标维护版本历史，查询时二分找到不超过目标版本的最后一次赋值。 |
| 35. 搜索插入位置 | 简单 | 版本查询需要边界二分，目标不是必须存在的快照记录，而是最近的较早记录。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！