设计一个支持 min、getLast、append、deleteLast 的数据结构，时间复杂度为 O(1)，内存范围为 n（不是 O(n)）+ O(1)

Question

我需要设计一个支持以下内容的数据结构：

getMinElement，getLastElement，insertElement，deleteLastElement- 在O(1)运行时。

内存以 n 为界（不是 O(n)）限制，即在给定时刻最多可以保留 n 个元素。加上 O(1) 内存。

（重要提示：指针也被视为 1，因此，例如链表是不可能的）。

例子：

insert(6)
min() -> 6
insert(10)
insert(5)
min() -> 5
insert(7)
delete()
min() -> 5
delete()
min() -> 6

Answer 1

我们将直接存储最新的最小值。这是 O(1) 空间。

\n\n

我们还将使用整数数组，因为这似乎是可变长度空间的唯一选择。但我们不会直接存储元素。相反，当我们插入一个元素时，我们将存储该元素与（先前的）最小值之间的差异。当我们删除一个元素时，如有必要，我们可以使用该差异来恢复先前的最小值。

\n\n

在Python中：

\n\n

class MinStorage:\n\n    def __init__(self):\n        self.offsets = []\n        self.min = None\n\n    def insertElement(self, element):\n        offset = 0 if self.min is None else (element - self.min)\n        self.offsets.append(offset)\n        if self.min is None or offset < 0:\n            self.min = element\n\n    def getMinElement(self):\n        return self.min\n\n    def getLastElement(self):\n        offset = self.offsets[-1]\n        if offset < 0:\n            # Last element defined a new minimum, so offset is an offset\n            # from the prior minimum, not an offset from self.min.\n            return self.min\n        else:\n            return self.min + offset\n\n    def deleteLastElement(self):\n        offset = self.offsets[-1]\n        self.offsets.pop()\n        if len(self.offsets) == 0:\n            self.min = None\n        if offset < 0:\n            self.min -= offset\n

\n\n

这里的版本允许任何无符号 16 位整数作为元素，并且仅在数组中存储无符号 16 位整数：

\n\n

class MinStorage:\n\n    Cap = 65536\n\n    def __init__(self):\n        self.offsets = []\n        self.min = None\n\n    def insertElement(self, element):\n        assert 0 <= element < self.Cap\n        offset = 0 if self.min is None else (element - self.min)\n        if offset < 0: offset += self.Cap\n        self.offsets.append(offset)\n        if self.min is None or element < self.min:\n            self.min = element\n\n    def getMinElement(self):\n        return self.min\n\n    def getLastElement(self):\n        element = self.__getLastElementUnchecked()\n        if element < self.min:\n            # Last element defined a new minimum, so offset is an offset\n            # from the prior minimum, not an offset from self.min.\n            return self.min\n        else:\n            return element\n\n    def deleteLastElement(self):\n        element = self.__getLastElementUnchecked()\n        self.offsets.pop()\n        if len(self.offsets) == 0:\n            self.min = None\n        elif element < self.min:\n            # Popped element defined a new minimum.\n            self.min = element\n\n    def __getLastElementUnchecked(self):\n        offset = self.offsets[-1]\n        element = self.min + offset\n        if element >= self.Cap:\n            element -= self.Cap\n        return element\n

\n\n

请注意，在具有上溢/下溢的无符号 16 位算术的语言中，您不需要涉及self.Cap. 在 C (\xc2\xa76.2.5/9) 和 C++ (\xc2\xa73.9.1/4) 中，需要无符号算术才能按需要运行。但是，Python 不支持无符号 16 位算术。

\n