原题链接：剑指 Offer 30. 包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 $O(1)$。
题目详解
这道题的难点在于调用 min 的复杂度也是 $O(1)$， 如果只是简单粗暴使用任何排序法，其复杂度至少都是$O(n\log n)$。但与此同时，我们的确需要一个容器来管理第一最小值、第二最小值……，并且他们在该容器内有序排列。单调栈似乎是个不错的选择。因此我们总的设计方案为，用一个普通栈来存储所有元素——保证pop、push的复杂度是$O(1)$，再用一个单调栈来处理min 函数——保证min的复杂是$O(1)$。
当push一个元素的时候，该把它放到哪个栈里呢？我们不得不分类讨论：
- 当普通栈是空的时候，单调栈也必然为空。因此，我们需要将新元素放到两个栈里。
- 当普通栈不是空的时候，此时我们需要考虑该元素和上一元素的大小关系
- 如果该元素比上一元素大，那么它必然不会影响最小值，因此只需将其放置于普通栈即可。
- 如果该元素比上一元素小，我们就得考虑它是否小于单调栈中的最小值（其实也就是所有元素的最小值），若小于还需将其放置于单调栈中。
最后我们还要处理pop，如果普通栈pop的元素与单调栈栈顶元素（最小值）一样，那么我们也得对单调栈进行pop。
代码实现
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
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <vector>
#include <stack>
#include <iostream>
using namespace std;
int main()
{
class MinStack
{
public:
stack<int> stack1, stack2;
MinStack() {}
void push(int x)
{
if (stack2.empty() || (x <= stack2.top()))
stack2.push(x);
stack1.push(x);
}
void pop()
{
int temp = stack1.top();
if (temp == stack2.top())
stack2.pop();
stack1.pop();
}
int top()
return stack1.top();
int min()
return stack2.top();
};
MinStack myStack;
myStack.push(-2);
myStack.push(0);
myStack.push(-3);
cout << myStack.min() << endl;
myStack.pop();
cout << myStack.top() << endl;
}
|
