题目链接：Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
这道题的要求是实现一种数据结构，使其在实现栈的功能的同时又能以O(1)时间返回最小值，并支持push(x)、pop()、top()、getMin()四种操作。
思路就是用1个栈s完成栈的操作，再利用一个栈mins维护最小值（其栈顶就为数据的最小值）：
- push(x)：将元素压入s中，同时比较x与mins的栈顶元素（如果民生为空，直接压入mins中）大小，将小的压入mins中；
- pop()：s和mins中均弹出元素即可；
- top()：返回s中的栈顶元素；
- getMin()：返回mins中的栈顶元素。
压栈的详细过程如下：
例如依次压入2、4、1、3，那么
压入2后：
| 2 | | 2 |
|---| |---|
s mins
压入4后：
| 4 | | 2 |
| 2 | | 2 |
|---| |---|
s mins
压入1后：
| 1 | | 1 |
| 4 | | 2 |
| 2 | | 2 |
|---| |---|
s mins
压入3后：
| 3 | | 1 |
| 1 | | 1 |
| 4 | | 2 |
| 2 | | 2 |
|---| |---|
s mins
不过上面有一个问题，细心观察就可以发现，就是mins中的1和2发生了重复，造成了空间浪费。要想避免这种浪费，可以对push和pop操作稍做处理：
- push(x)：将元素压入s中，而只有当mins为空或者mins的栈顶元素大于等于x的时候才压入栈，这样就可以避免重复在mins中压入相同的最小值；
- pop()：s中弹出元素，而只有在mins的栈顶元素与s中要弹栈的元素相等的时候，mins才弹栈，因为此时说明mins中的栈顶元素是在s中压入栈之后的最小值，需要弹出。
这样，对于上面那个例子，情况如下：
例如依次压入2、4、1、3，那么
压入2后：
| 2 | | 2 |
|---| |---|
s mins
压入4后（由于4大于mins的栈顶元素2，因此mins不进行压栈操作）：
| 4 |
| 2 | | 2 |
|---| |---|
s mins
压入1后（由于1小于mins的栈顶元素2，因此把1压入mins中）：
| 1 |
| 4 | | 1 |
| 2 | | 2 |
|---| |---|
s mins
压入3后（同上面压入4情形，mins不进行压栈操作）：
| 3 |
| 1 |
| 4 | | 1 |
| 2 | | 2 |
|---| |---|
s mins
而对于弹栈操作：
1次pop后（由于s的栈顶元素于mins的栈顶元素不同，因此mins不进行弹栈操作）：
| 1 |
| 4 | | 1 |
| 2 | | 2 |
|---| |---|
s mins
2次pop后（由于s的栈顶元素于mins的栈顶元素相同，因此mins需要弹栈操作）：
| 4 |
| 2 | | 2 |
|---| |---|
s mins
3次pop后：
| 2 | | 2 |
|---| |---|
s mins
4次pop后：
|---| |---|
s mins
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack
{
stack<int> s;
stack<int> mins;
public:
void push(int x)
{
if(mins.empty() || x <= mins.top())
mins.push(x);
s.push(x);
}
void pop()
{
if(s.top() == mins.top())
mins.pop();
s.pop();
}
int top()
{
return s.top();
}
int getMin()
{
return mins.top();
}
};