方法一:辅助栈
创建一个辅助栈,保存最小值,每次入栈的时候,我们把辅助栈顶和要入的值两者中的最小值入栈
class MinStack
{
private:
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack()
{
min_stack.emplace(INT_MAX);
}
void push(int val)
{
min_stack.emplace(min(min_stack.top(), val));
x_stack.emplace(val);
}
void pop()
{
x_stack.pop();
min_stack.pop();
}
int top()
{
return x_stack.top();
}
int getMin()
{
return min_stack.top();
}
};
时间复杂度:对于题目中的所有 *** 作,时间复杂度均为 O(1)。因为栈的插入、删除与读取 *** 作都是 O(1),我们定义的每个 *** 作最多调用栈 *** 作两次。
空间复杂度:O(n),其中 nn 为总 *** 作数。最坏情况下,我们会连续插入 n 个元素,此时两个栈占用的空间为 O(n)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)