LinkedIn 电面System & Infra

来一个新鲜的跪经。

实现MaxStac

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

linked list

这道题如果popMax要求是O(1)的话，我觉得必须得维护一个sorted list, 同时还要维护一个stack，这两个都是链表，并且两个表中对应的节点都有双向指针相连，可以保证push是O(n), 其他操作都是O(1).
Correct me if I am wrong..

楼主po max 怎么做到o(1) 用treeset不是就o(logn) 了吗?

啊好吧我来update一下 居然过了 大周五五点半hr打电话来告诉过了也是敬业。。。看来会不会做大声讲出思路，积极沟通是重要的

和min stack一样吧

nestwood 发表于 2017-2-18 15:57
和min stack一样吧

不能吧....有popMax 跟peakMax 的要求...

lz是最棒的！！！加油，一定可以拿到心仪的offer！！！！

恭喜LZ。这个题挺难啊，LZ能share一下detail吗

say543 发表于 2017-2-18 15:30
楼主po max 怎么做到o(1) 用treeset不是就o(logn) 了吗?

同问，treeset 是个balanced BST, search, insertion, deletion 都是O(logn), popMax后需要维护原树的平衡性，也得O(logn)吧？如何做到O(1) 的？

这个题应该就是min stack一样的解法吧