Cinte's Leetcode Record
0%

面试题 03.03. 堆盘子

Posted on Edited on In Disqus:
Symbols count in article: 2.5k Reading time ≈ 2 mins.

面试题 03.03. 堆盘子

双向链表

用双向链表来维护堆栈之间的顺序，用cur指针来指向当前的堆栈。每次通过顺序遍历来获取到第index个栈。通过删除节点来作为删除栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class StackOfPlates {
public:
    StackOfPlates(int cap) : head(new Node()), tail(new Node()), cap(cap){
        head->next = tail;
        tail->prev = head;
        cur = head;
    }
    // O(1)
    void push(int val) {
        if(cap == 0)
            return;
        if(isFull(cur))
        {
            cur->next = new Node(cur, cur->next);
            cur = cur->next;
        }
        cur->s.push(val);
    }
    // O(1)
    int pop() {
        if(cur == head)
            return -1;
        auto ret = cur->s.top();
        cur->s.pop();
        if(cur->s.empty())
        {
            auto tmp = cur;
            cur = cur->prev;
            deleteNode(tmp);
        }
        return ret;
    }
    // O(index)
    int popAt(int index) {
        Node* tmp = head;
        for(int i = 0; i <= index; ++i)
        {
            tmp = tmp->next;
            if(tmp == tail)
                return -1;
        }
        auto ret = tmp->s.top();
        tmp->s.pop();
        if(tmp->s.empty())
        {
            if(cur == tmp)
                cur = tmp->prev;
            deleteNode(tmp);
        }
        return ret;
    }
private:
    struct Node 
    {
        stack<int> s;
        Node* prev;
        Node* next;
        Node() = default;
        Node(Node* prev, Node* next) : prev(prev), next(next) {}
    };
    Node *head, *tail;
    Node *cur;
    int cap;
    bool isFull(Node* node)
    {
        if(node == head)
            return true;
        return node->s.size() == cap;
    }
    void deleteNode(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */
使用vector来存储stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class StackOfPlates {
public:
    StackOfPlates(int cap) : cap(cap) {

    }
    // O(1)
    void push(int val) {
        if(cap == 0)
            return;
        if(stacks.empty() || stacks.back().size() == cap)
            stacks.push_back(stack<int>());
        stacks.back().push(val);
    }
    // o(1)
    int pop() {
        if(stacks.empty())
            return -1;
        auto ret = stacks.back().top();
        stacks.back().pop();
        if(stacks.back().empty())
            stacks.pop_back();
        return ret;
    }
    // o(1), 最坏情况o(n)
    int popAt(int index) {
        if(index >= stacks.size())
            return -1;
        auto ret = stacks[index].top();
        stacks[index].pop();
        if(stacks[index].empty())
            stacks.erase(stacks.begin() + index);
        return ret;
    }
private:
    vector<stack<int>> stacks;
    int cap;
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */