算法与数据结构（最小栈）

题目

思路

为了返回栈中的最小元素，我们需要额外维护一个辅助栈 min_stack，它的作用是记录当前栈中的最小值。

min_stack的作用：

 min_stack的栈顶元素始终是当前栈 st 中的最小值。

   每当st中压入一个新元素时，如果这个元素小于等于 min_stack 的栈顶元素，就将它也压入 min_stack。

   每当st中弹出一个元素时，如果这个元素等于 min_stack 的栈顶元素，就将 min_stack 的栈顶元素也会弹出。

代码

class MinStack {
public:/** initialize your data structure here. */stack<int> st;stack<int> min_stack;MinStack() {}void push(int x) {st.push(x);if(min_stack.empty() || min_stack.top() >= x)min_stack.push(x);}void pop() {if(min_stack.top() == st.top())min_stack.pop();st.pop();}int top() {return st.top();}int getMin() {return min_stack.top();}
};