1146. Snapshot Array¶
题目信息¶
- 题号:
1146
- 难度:
Medium
- 主题:
设计题、版本快照、历史查询
- 原题:
- 重点:
数组初值全为
0;snap保存当前状态并返回递增编号,get查询指定快照中的历史值
题目重述¶
实现 SnapshotArray 类。构造函数接收数组长度 length,初始所有位置均为 0。set(index, val) 修改当前版本指定位置的值;snap() 保存当前数组状态,并返回该快照的编号,编号从 0 开始依次递增。
get(index, snap_id) 返回指定下标在编号为 snap_id 的快照中的值。快照创建后的修改不能影响已有快照。
1 <= length <= 5 * 10^4,0 <= index < length,0 <= val <= 10^9;全部 set、snap 和 get 调用总数不超过 5 * 10^4,查询的快照编号保证有效。
自建示例¶
快照保留修改前的历史值:
输入:
["SnapshotArray","set","snap","set","get","snap","get"]
[[2],[0,4],[],[0,7],[0,0],[],[1,1]]
输出:[null,null,0,null,4,1,0]
解释:快照 0 保存下标 0 的值 4;之后改为 7 不影响旧快照。下标 1 从未修改,在快照 1 中仍为 0。
同一快照前多次设置只保留最终值:
输入:
["SnapshotArray","set","set","snap","get"]
[[1],[0,2],[0,3],[],[0,0]]
输出:[null,null,null,0,3]
解释:创建快照前下标 0 的最后一次赋值为 3,因此快照 0 中查询得到 3。