脸家店面

建两个list可行吧，一个存末尾大的，一个存前边小的，然后merge

lz可以给一个例子吗

贴个解法  觉得对的话求加分

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

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

wtcupup 发表于 2018-8-22 11:06
LZ怎么做的？

抛个砖，大家认为对的话，求赏点米下锅

按照理解应该是，get() 会随机的从两端往中间取数，直到isEmpty()。
假设现在先后取到了两个数 a,b ；只需记住a先于b取到就行，然后就可以判断了

1) a < b;  那么a肯定是来自左端，因为若a来自右端，不论b来自哪边都是要小于a的，那么直接将a输出就行（append到一个Q的最后面）
2) a > b;  同样的分析，a肯定来自右端，右端的数需要先存起来不能直接输出 （push到一个stack中）

等到 isEmpty() 后，将stack的数pop出来并append到 Q的后面就行了

为什么不用bst呢？
每次插入都是O（lgN), 叫最大最小也是O (lgN)， 输出所有O(N).
因为需要O(1)?