LinkedIn 电面System & Infra

athenangel 发表于 2017-3-6 03:02
我觉得是不是用个doubly linked list + priority queue
这样peekMax 和 popMax酒是 o(1)了

我又看了一遍 题目。
只要求popmax和peakmax是o1。并没有说要求普通pop是o1。所以bst是可以的。

heap的popmax需要删除顶，需要log n的操作 是不行的

最简单的不是把push和pop变成linear的吗？

补充内容 (2017-3-17 14:48):
MaxStack如果用hashMap+doublyList的话可以变成log(n)

如果真的如楼主所说有 popMax， 这题出的就不对。 就违背了栈的基本原则 FIFO。LC的min stack是合理的。