题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
解题
方法一：辅助栈1
class MinStack { private: stack<int> st1; stack<int> st2; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { st1.push(x); if(st2.empty()||st2.top()>=x){ st2.push(x); } } void pop() { if(st1.top()==st2.top()){ st1.pop(); st2.pop(); } else{ st1.pop(); } } int top() { return st1.top(); } int min() { return st2.top(); } };
方法二：辅助栈2
一个栈是主栈 stackstack，另一个是辅助栈 minStackminStack，用于存放对应主栈不同时期的最小值。
class MinStack { stack<int> x_stack; stack<int> min_stack; public: MinStack() { min_stack.push(INT_MAX); } void push(int x) { x_stack.push(x); min_stack.push(std::min(min_stack.top(), x)); } void pop() { x_stack.pop(); min_stack.pop(); } int top() { return x_stack.top(); } int min() { return min_stack.top(); } };
