题目定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
难点和坑点
1.使用两个栈实现min函数的同时满足复杂度
2.注意在有pop操作并且需要条件判断时注意先判断操作然后在pop操作
3.在进行入栈操作时因为要判断value是否是最小值,如果是最小值就要同时入第二个栈,在由于我们是将value和第二个栈的栈顶元素比较,当第二个栈初试为空时比较失败会导致溢出等error,所以在push操作时要先判断第二个栈是否为空并进行复制操作;
class Solution {
public:
stack<int> stack1,stack2;
void push(int value) {
stack1.push(value);
if(stack2.empty())
stack2.push(value);
else if(stack2.top() >= value)
stack2.push(value);
}
void pop() {
if(stack1.top()==stack2.top())
stack2.pop();
stack1.pop();
}
int top() {
return stack1.top();
}
int min() {
return stack2.top();
}
};
网友评论