Linkedin电面+onsite

maxStack那题应该是写一个linkedlist来当作stack，然后再用个Arraylist存储最大node的指针，然后push过程中同时生成存元素的linkedlist和存最大node的Arraylist。popMax操作直接根据最大node的指针把那个node从linkedlist中删除就好了， 删除操作O(1)。java写的话要自己写一个linkedlist，比较麻烦，C++可以直接使用std::list，然后存储最大node的iterator，相对好写些

补充内容 (2017-1-25 19:53):
不好意思，想简单了，这段写得不对

simonwoo 发表于 2017-1-25 17:56
"popMax操作直接根据最大node的指针把那个node从linkedlist中删除就好了"

可以连续删除两次吗?你怎么 ...

嗯，你说的对，我想简单了，没有考虑到popMax之后的max维护

plp2016 发表于 2016-12-2 12:04
我觉得他应该是要求popmax那里要o1 不算上treemap或者heap的insert和remove吧 到最后他也没说清楚我也没 ...

如果push 和popmax都能O(1）的话，那么可以使用这个东西去进行基于比较的排序，然后复杂度是O(n)（把 所有元素放进去，然后popmax出来就完了。）所以我觉得是不可能的。求喷。

304671127 发表于 2016-11-26 11:00
popmax 那题用两个stack不就可以了吗，一个记录正常数值，一个记录到目前的max值，然后要那个就pop那个。   ...

我也觉得是stack.请问这样做什么错了？

plp2016 发表于 2016-12-2 12:08
那个popmax的题大家也不要太纠结了 我没有见过这个的面经 那个国男没有看他们的题库 几道题都是他在那儿 ...

我觉得popmax() O(1)这个题目就是个流氓题目

楼里有个兄弟说得很对，如果push() 和 popmax() 都能做到O(1)的话，你可以拿这个来实现很general的O(n)复杂度的sorting，这明显不可能

所以这其实就是牺牲push()和pop()的复杂度来实现popmax() O(1)，我的一个做法用两个linked list:
list<int> l1;
list<pair<int,list<int>::iterator>> l2;
这里l1就实现基本的stack，l2把l1里面的所有value排序，并且记住这个value在l1里面的位置，这样peek()和peekMax()都是O(1)，popMax()是O(1)，但push()和pop()都是O(N)

所以我感觉这种做法就是耍流氓

kqxqx 发表于 2017-8-27 01:57
我觉得popmax() O(1)这个题目就是个流氓题目

楼里有个兄弟说得很对，如果push() 和 popmax() 都能做到 ...

可以再优化一下：list<int> l1和上面一样，按照value来的顺序实现一个普通stack，list<int> l2存l1中所有值排序后的新链表，再来一个unordered_map<int, pair<list<int>::iterator, list<int>::iterator>>记录每个值在l1, l2中的对应位置，这样peek()/peekMax()还是O(1), pop()和popMax()都是O(1)了，但是push()还是O(N)

pat pat. move on.........

plp2016 发表于 2016-11-20 02:24
一开始什么要求都没有 就问我知不知道猜词游戏 解释了一下 说让设计一个web上玩的
于是一开始我就写了一 ...

问下楼主什么叫把代码下载到本地？谢谢