LinkedIn 电面System & Infra

ilovetennis 发表于 2017-2-21 07:03
这道题如果popMax要求是O(1)的话，我觉得必须得维护一个sorted list, 同时还要维护一个stack，这两个都是链 ...

这想法好像能work 我写个代码看看...

我感觉和min stack一样吧？见这个链接：https://discuss.leetcode.com/topic/7020/java-accepted-solution-using-one-stack
链接里是min stack的，只用一个stack，不用treeset或者double linked list。把它翻成max就可以了吧？
Kindly correct me if I am wrong...Thanks!

dlys3000 发表于 2017-2-27 10:48
我感觉和min stack一样吧？见这个链接：https://discuss.leetcode.com/topic/7020/java-accepted-solution- ...

我觉得也是跟 min stack一样
觉得不一样的 说说 idea

需要PeakMax和PopMax LC的min stack不需要pop吧

lianghuang216 发表于 2017-3-2 19:30
需要PeakMax和PopMax LC的min stack不需要pop吧

有pop

dlys3000 发表于 2017-3-3 14:56
有pop

public class MinStack {

    /** initialize your data structure here. */
    public MinStack() {
        
    }
   
    public void push(int x) {
        
    }
   
    public void pop() {
        
    }
   
    public int top() {
        
    }
   
    public int getMin() {
        
    }
}

LC 是POP 这道题需要PopMAX 和普通的POP 都要实现。

比如你PopMAX 但是max并不是stack顶上的，怎么从stack中删除这个max？

ok
这样啊。。。确实

lianghuang216 发表于 2017-3-4 02:47
public class MinStack {

    /** initialize your data structure here. */

楼主能不能展开说说怎么做? thanks

好题
感觉lz的做法是对的。
不知道treeset是什么。 但是基本想法就是：
一个linkedlist存原stack，插入删除都是o1
然后维护一个有序序列，因为有序，所以二分插入可以做到log n, 取最大是o1 也就是popMax，这个数据结构可以用BST，我猜想就是lz说的TreeSet？
综合就是插入log n， popmax是1，但是我不理解的是pop为什么o1的？ 照理说bst应该是logn的删除，难道Treeset 有什么特性？

30048686 发表于 2017-3-5 16:02
好题
感觉lz的做法是对的。
不知道treeset是什么。 但是基本想法就是：

我觉得是不是用个doubly linked list + priority queue
这样peekMax 和 popMax酒是 o(1)了