面试金典题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();
*/这道题的思路很简单，就是同时定义两个栈，一个存储元素，一个存储当前栈中最小值。因此最小栈的栈顶元素永远是当前栈中的最小元素。