定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.
思路：
用一个栈来保存push和pop的数。push和pop的时间复杂度不用多管，直接就符合题意。问题在于min函数。如果用一个变量x记录最小值，则可以每次都在O(1)的时间内执行min。但是如果pop的就是当前的最小值，再直接返回x就无法正确返回最小值。所以栈里存的数要跟最小值联系上。每次push和pop的时候去更新最小值。这时差值就非常适合。如果栈里保存的数就是每次push的数和最小值的差值，那么push和pop的时候，就可以正常执行，并且可以正确维护最小值
代码：
class MinStack {
private:
//有加减乘除操作都有可能造成溢出，结果不对。所以用long long类型
stack<long long> stk;
long long minX = 0;
public:
/** initialize your data structure here. */
MinStack() {
}
//push差值，更新最小值
void push(int x) {
if(stk.empty()) {
minX = x;
}
stk.push(x - minX);
minX = minX < x ? minX: x;
}
//pop正常执行，有必要时，更新最小值
void pop() {
if(!stk.empty()) {
if(stk.top() < 0) {
minX = minX - stk.top();
}
stk.pop();
}
}
//如果当前的差值大于0，那么返回最小值和栈顶的和，否则，直接返回最小值，因为此时最小值就是原始的x
int top() {
if (!stk.empty()) {
if(stk.top() > 0) {
return minX + stk.top();
}
else {
return minX;
}
}
return INT_MAX;
}
//直接返回最小值
int min() {
if(stk.empty()) {
return INT_MAX;
}
return minX;
}
};