# 问题 原题链接：[https://leetcode.com/problems/max-stack/](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. # 分析过程 - 输入：栈操作。 - 输出：一个最大栈，额外提供`peakMax`和`popMax`方法。 - 思路：额外使用一个辅助栈，保存当前情况下的最大数。见注释。 # 解决方法 ```cpp 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; }; ```