【HARD】Max Stack

发布于: 2019-03-03 19:02
阅读: 17
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/max-stack/

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

  • push(x) -- Push element x onto stack.
  • pop() -- Remove the element on top of the stack and return it.
  • top() -- Get the element on the top.
  • peekMax() -- Retrieve the maximum element in the stack.
  • 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

Note:

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

分析过程

  • 输入:栈操作。
  • 输出:一个最大栈,额外提供peakMaxpopMax方法。
  • 思路:额外使用一个辅助栈,保存当前情况下的最大数。见注释。

解决方法

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        _allNumStack.push(x);
        
        // 如果入栈的元素是历史以来最大的(包括等于)
        if (_maxNumStack.empty() || x >= _maxNumStack.top()) {
            // 入最大数栈
            _maxNumStack.push(x);
        }
    }
    
    int pop() {
        int topValue = top();
        _allNumStack.pop();
        
        // 如果取出的数是当前最大的,最大数栈也需要弹出
        if (topValue == _maxNumStack.top()) {
            _maxNumStack.pop();
        }
        
        return topValue;
    }
    
    int top() {
        return _allNumStack.top();
    }
    
    int peekMax() {
        return _maxNumStack.top();
    }
    
    int popMax() {
        int maxValue = _maxNumStack.top();
        _maxNumStack.pop();
        
        // 使用临时栈,在保存所有元素的栈里找到最大数
        stack<int> tmp;
        while (_allNumStack.top() != maxValue) {
            tmp.push(_allNumStack.top());
            _allNumStack.pop();
        }
        // 把这个最大数弹出
        _allNumStack.pop();
        // 再把数据从临时栈恢复回来
        while (!tmp.empty()) {
            push(tmp.top());
            tmp.pop();
        }
        return maxValue;
    }
    
private:
    // 保存所有的元素的栈
    stack<int> _allNumStack;
    // 保存当前最大的数的栈
    stack<int> _maxNumStack;
};

Thanks for reading.

All the best wishes for you! 💕