美文网首页
WEEK#19 Max Stack

WEEK#19 Max Stack

作者: DarkKnightRedoc | 来源:发表于2018-01-12 09:40 被阅读0次

    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(); -> 5
    stack.popMax(); -> 5
    stack.top(); -> 1
    stack.peekMax(); -> 5
    stack.pop(); -> 1
    stack.top(); -> 5
    </pre>

    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(),随时随地可以查看和返回最大值。之前有一道很类似的题Min Stack,所以我们可以借鉴那道题的解法,使用两个栈来模拟,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<int> 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<int> s1, s2;
    };
    

    相关文章

      网友评论

          本文标题:WEEK#19 Max Stack

          本文链接:https://www.haomeiwen.com/subject/zdbxoxtx.html