716.Max Stack¶
Tags: Easy
Stack
Design
Links: https://www.lintcode.com/problem/max-stack/description(LeetCode上锁,用LintCode代替)
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.
这道题在LintCode竟然是Hard,其实只是在Min Stack的基础上增加了一个要求删除最大值的操作,比如依次推入5,3,3,最大值为5,需要删除5,那么其实可以用一个临时栈将3,3存储,然后删掉5后,再把临时存储的数据加入到原来的栈。另外,这里的pop
还需要返回被删除的元素,不再是void
了。
class MaxStack {
stack<int> s1, s2;
public:
/** initialize your data structure here. */
MaxStack() {}
void push(int x) {
if (s2.empty() || x >= s2.top()) s2.push(x);
s1.push(x);
}
int pop() {
if (s1.empty()) return -1;
int res = s1.top();
s1.pop();
if (res == s2.top()) s2.pop();
return res;
}
int top() {
if (s1.empty()) return -1;
return s1.top();
}
int peekMax() {
if (s2.empty()) return -1;
return s2.top();
}
int popMax() {
if (s2.empty()) return -1;
int res = s2.top();
s2.pop();
stack<int> tmp;
while (s1.top() != res) {
tmp.push(s1.top());
s1.pop();
}
s1.pop();
while (!tmp.empty()) {
push(tmp.top());
tmp.pop();
}
return res;
}
};
/**
* Your MaxStack object will be instantiated and called as such:
* MaxStack* obj = new MaxStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->peekMax();
* int param_5 = obj->popMax();
*/
数据更新后出错的测试用例:
["MaxStack","push","push","popMax","peekMax"]
[[],[5],[1],[],[]]
Output: [null,null,null,5,-1]
Judge: [null,null,null,5,1]
注意删除最大值需要重新来一次push
。