Design a max stack that supports push, pop, top, peekMax and popMax.

 

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

 

Example 1:

MaxStack stack = new MaxStack();stack.push(5); stack.push(1);stack.push(5);stack.top(); -> 5stack.popMax(); -> 5stack.top(); -> 1stack.peekMax(); -> 5stack.pop(); -> 1stack.top(); -> 5

 

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

 

这道题让我们实现一个最大栈，包含一般栈的功能，但是还新加了两个功能peekMax()和popMax()，随时随地可以查看和返回最大值。之前有一道很类似的题，所以我们可以借鉴那道题的解法，使用两个栈来模拟，s1为普通的栈，用来保存所有的数字，而s2为最大栈，用来保存出现的最大的数字。

在push()函数中，我们先来看s2，如果s2为空，或者s2的栈顶元素小于等于x，将x压入s2中。因为s2保存的是目前为止最大的数字，所以一旦新数字大于等于栈顶元素，说明遇到更大的数字了，压入栈。然后将数组压入s1，s1保存所有的数字，所以都得压入栈。

在pop()函数中，当s2的栈顶元素和s1的栈顶元素相同时，我们要移除s2的栈顶元素，因为一个数字不在s1中了，就不能在s2中。然后取出s1的栈顶元素，并移除s1，返回即可。

在top()函数中，直接返回s1的top()函数即可。

在peekMax()函数中，直接返回s2的top()函数即可。

在popMax()函数中，先将s2的栈顶元素保存到一个变量mx中，然后我们要在s1中删除这个元素，由于栈无法直接定位元素，所以我们用一个临时栈t，将s1的出栈元素保存到临时栈t中，当s1的栈顶元素和s2的栈顶元素相同时退出while循环，此时我们在s1中找到了s2的栈顶元素，分别将s1和s2的栈顶元素移除，然后要做的是将临时栈t中的元素加回s1中，注意此时容易犯的一个错误是，没有同时更新s2，所以我们直接调用push()函数即可，参见代码如下：

 

解法一：

class MaxStack {public:    /** initialize your data structure here. */    MaxStack() {}        void push(int x) {        if (s2.empty() || s2.top() <= x) s2.push(x);        s1.push(x);    }        int pop() {        if (!s2.empty() && s2.top() == s1.top()) s2.pop();        int t = s1.top(); s1.pop();        return t;    }        int top() {        return s1.top();    }        int peekMax() {        return s2.top();    }        int popMax() {        int mx = s2.top();        stack
      
        t;        while (s1.top() != s2.top()) {            t.push(s1.top()); s1.pop();        }        s1.pop(); s2.pop();        while (!t.empty()) {            push(t.top()); t.pop();        }        return mx;    }private:    stack
       
         s1, s2;};
       
      

 

下面这种解法没有利用一般的stack，而是建立一种较为复杂的数据结构，首先用一个list链表来保存所有的数字，然后建立一个数字和包含所有相同的数字的位置iterator的向量容器的映射map。

在push()函数中，把新数字加到list表头，然后把数字x的位置iterator加到数字映射的向量容器的末尾。

在pop()函数中，先得到表头数字，然后把该数字对应的iterator向量容器的末尾元素删掉，如果此时向量容器为空了，将这个映射直接删除，移除表头数字，返回该数字即可。

在top()函数中，直接返回表头数字即可。

在peekMax()函数中，因为map是按key值自动排序的，直接尾映射的key值即可。

在popMax()函数中，首先保存尾映射的key值，也就是最大值到变量x中，然后在其对应的向量容器的末尾取出其在list中的iterator。然后删除该向量容器的尾元素，如果此时向量容器为空了，将这个映射直接删除。根据之前取出的iterator，在list中删除对应的数字，返回x即可，参见代码如下：

 

解法二：

class MaxStack {public:    /** initialize your data structure here. */    MaxStack() {}        void push(int x) {        v.insert(v.begin(), x);        m[x].push_back(v.begin());    }        int pop() {        int x = *v.begin();        m[x].pop_back();        if (m[x].empty()) m.erase(x);        v.erase(v.begin());        return x;    }        int top() {        return *v.begin();    }        int peekMax() {        return m.rbegin()->first;    }        int popMax() {        int x = m.rbegin()->first;        auto it = m[x].back();        m[x].pop_back();        if (m[x].empty()) m.erase(x);        v.erase(it);        return x;    }private:    list
      
        v;    map
       

::iterator>> m;};

 

类似题目：

 

参考资料：