332-Leetcode 最小栈

方法一：辅助栈

创建一个辅助栈，保存最小值，每次入栈的时候，我们把辅助栈顶和要入的值两者中的最小值入栈

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)