面试题21:包含min函数的栈

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min,push及pop函数的时间复杂度都是O(1)。


分析

栈应该是我们很熟悉的一种数据结构了,它是一种“后进先出”的数据结构,并且只能在栈的一端(栈顶)进行操作。所以其push和pop操作的时间复杂度都是O(1)。如果题目没有要求min函数的时间复杂度的话,我们可以在min函数里面遍历所有的元素并将其保存起来,找到最小的元素后再将所有元素以相反的顺序放回去。但现在这种方案显然不行。

我们可以定义两个栈,一个存放我们需要的元素,称为元素栈。另一个存放当前元素栈里面最小的一个元素值,称为最小值栈。这样,当调用min函数时,直接返回最小值栈的栈顶就可以了,达到了O(1)的时间复杂度。这是一个“以空间换时间”的方法。

这样,在插入元素时,先将其插入元素栈里,并判断该元素是否小于最小值栈的栈顶元素,若小于,则将该元素插入最小值栈,否则,将最小值栈的栈顶元素在此插入最小值栈。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
43
44
45
46
47
48
49
50
51
52
class StackIsEmpty{};
template<typename T>
class MyStack{
public:
void push(const T& t)
{
if(s.empty())
{
m.push(t);
}
else
{
if(t<m.top())
{
m.push(t);
}
else
{
m.push(m.top());
}
}
s.push(t);
}
void pop()
{
if(!s.empty())
{
s.pop();
m.pop();
}
else
throw StackIsEmpty();
}
T& min()
{
if(!s.empty())
{
return m.top();
}
else
throw StackIsEmpty();
}
bool empty()
{
return s.empty();
}
private:
stack<T> s;
stack<T> m;//min
};

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>