关键词：排序
题目：最小栈
方法一：在记录这个数的同时，记录目前的最小值。看了提示才写出来的。
方法二：辅助栈。辅助栈保持非严格递减。看了k神的答案。
方法一：
一开始没想到怎么存最小，看了评论的提示才想到的。
思路：
关键：一个栈的一个元素存两样大小：这个数本身，包括这个数在内，目前栈的最小值。
存数的同时存截至到这个数为止的最小数。
注意：min的比较是和栈的前一个min比，不是和全局的min比。
min=(x<stack.back()[1])?x:stack.back()[1];如果全局的min是1，可是1已经被pop了，但是这个min的记录还会是1，就会出错。
复杂度计算：
时间复杂度O(n)
空间复杂度O(n)
代码：
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if(stack.empty())
min=x;
else
min=(x<stack.back()[1])?x:stack.back()[1];
stack.push_back({x,min});
}
void pop() {
stack.pop_back();
}
int top() {
return stack.back()[0];
}
int getMin() {
return stack.back()[1];
}
private:
vector<vector<int>> stack;
int min=INT_MAX;
};
/**
* 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();
*/方法二：
看了k神。用了两个栈，A栈正常存数，B栈存最小值，B栈要保持非严格递减。
思路：
入栈的时候，还需要维护辅助栈。为什么要维护非严格降序的辅助栈：
1、如果：
B.top() >= x则要把x存进B里面，保持非严格降序，这个时候x就是B里面最小的。
2、如果：
B.top() < x则不用存x，因为前面已经有B.top()小于x了，x无论怎么样都不可能是最小值。
出栈的时候，如果B.top()等于要A出栈的那个数，那么B也要跟着出栈。理由当然是因为那个数跑了，所以B当然要一起删掉。
非严格降序：
复杂度计算：
时间复杂度O(n)
空间复杂度O(n)
代码：
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
A.push(x);
if(B.empty()||x<=B.top())
B.push(x);
}
void pop() {
if(A.top()==B.top())
B.pop();
A.pop();
}
int top() {
return A.top();
}
int getMin() {
return B.top();
}
private:
stack<int> A;
stack<int> B;
};
/**
* 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();
*/
