如何降低SnapshotArray实现的内存占用以解决MLE问题？

你当前的代码每次调用snap()都会复制整个数组到hash中，当数组长度很大且快照次数较多时，会导致内存占用呈线性增长，最终触发MLE。核心问题是重复存储了大量未修改的元素——大部分元素在多次快照中值都没有变化，完全没必要每次都复制。

优化思路 #

不为每个快照存储完整数组，而是为每个索引单独维护其修改历史：每个索引对应一个列表，存储(快照ID, 值)的记录。只有当索引的值被修改时，才新增一条记录；未被修改的索引默认值为0，无需重复存储。查询时通过二分查找快速定位到指定快照ID对应的历史值。

优化后的代码 #

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        # 每个索引维护一个列表，存储(snap_id, value)，初始值为(0, 0)
        self.history = [[(0, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # 获取当前索引的最后一条记录
        last_snap, last_val = self.history[index][-1]
        # 如果当前还在同一个快照周期内，直接更新最后一条记录的值
        if last_snap == self.snap_id:
            self.history[index][-1] = (self.snap_id, val)
        else:
            # 新增一条当前快照ID的记录
            self.history[index].append((self.snap_id, val))

    def snap(self) -> int:
        # 只需要递增快照ID，无需复制数组
        res = self.snap_id
        self.snap_id += 1
        return res

    def get(self, index: int, snap_id: int) -> int:
        # 在当前索引的历史记录中二分查找最大的<=snap_id的记录
        records = self.history[index]
        left, right = 0, len(records) - 1
        ans = 0
        while left <= right:
            mid = (left + right) // 2
            if records[mid][0] <= snap_id:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return records[ans][1]

内存优化原理 #

• 原方案每次快照占用O(n)内存（n为数组长度），m次快照总内存为O(n*m)
• 优化方案仅存储被修改的记录，总内存为O(k)（k为所有索引被修改的总次数），当k远小于n*m时，内存占用大幅降低
• 查询时通过二分查找保证了O(logk)的时间复杂度，完全满足题目要求

内容的提问来源于stack exchange，提问作者AlwaysneedsHelp