面试金典题3.2

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

class MinStack {
public://定义两个栈，一个用于存储元素，一个用于存最小值stack<int> mystack;stack<int> minstack;/** initialize your data structure here. *///先将最大值入最小值的栈，方便第一个比较MinStack() {minstack.push(INT_MAX);}//同时将元素加入两个栈void push(int x) {mystack.push(x);//比较入栈元素和当前栈顶元素，将最小值入栈minstack.push(min(x,minstack.top()));}//同时让两个栈的栈顶元素出栈void pop() {mystack.pop();minstack.pop();}//返回栈顶元素int top() {return mystack.top();}//返回最小栈的栈顶元素，即当前栈中的最小值int getMin() {return minstack.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

这道题的思路很简单，就是同时定义两个栈，一个存储元素，一个存储当前栈中最小值。因此最小栈的栈顶元素永远是当前栈中的最小元素。