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

题目

思路

为了返回栈中的最小元素，我们需要额外维护一个辅助栈 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(); } };