题目
原文：
How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
译文：
实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值。 push，pop和min函数的时间复杂度都为O(1)。
解答
看到这个题目最直接的反应是用一个变量来保存当前栈的最小值，让我们来看看这样可行否？ 如果栈一直push那是没有问题，入栈元素如果比当前最小值还小，那就更新当前最小值。 可是如果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
const int MAX_INT = ~(1<<31);//2147483647
typedef struct node{
int val, min;
}node;
class StackWithMin{
public:
StackWithMin(int size=1000){
buf = new node[size];
buf[0].min = MAX_INT;
cur = 0;
}
~StackWithMin(){
delete[] buf;
}
void push(int val){
buf[++cur].val = val;
if(val<buf[cur-1].min) buf[cur].min = val;
else buf[cur].min = buf[cur-1].min;
}
void pop(){
--cur;
}
int top(){
return buf[cur].val;
}
bool empty(){
return cur==0;
}
int min(){
return buf[cur].min;
}
private:
node *buf;
int cur;
};
这种实现方式有一个明显的问题：数据冗余。比如说，栈里的数据从栈底到栈顶是1到10000， 那么，每个结点保存的最小值都是1，也就是保存了1的10000份拷贝，有这个必要吗？ 直觉告诉我们应该是没必要的，我们应该可以想办法只保留一份1的拷贝， 然后如果结点是这些1到10000，就正确地返回这个最小值。这个要怎么做呢？ 我们假设除了用一个栈s1来保存数据，还用另一个栈s2来保存这些非冗余最小值。那么， 当我们将数据压到要s1时，同时将它和s2的栈顶元素比较，如果不大于s2的栈顶元素， 那么将当前值也压入s2中。这样一来，s2中保存的就是一个阶段性最小值。 即s2中的每个值都是s1中栈底到达某个位置的最小值。那么，如果执行pop操作呢？ 执行pop操作除了将s1中的栈顶元素出栈，还要将它和s2中的栈顶元素比较，如果相等， 说明这个值是栈底到栈顶的最小值，而它出栈后，最小值就不再是它了。所以， s2也要将栈顶元素出栈，新的栈顶元素将对应s1剩下元素中新的最小值。
代码如下：
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
53
54
55
56
57
58
59
class stack{
public:
stack(int size=1000){
buf = new int[size];
cur = -1;
}
~stack(){
delete[] buf;
}
void push(int val){
buf[++cur] = val;
}
void pop(){
--cur;
}
int top(){
return buf[cur];
}
bool empty(){
return cur==-1;
}
private:
int *buf;
int cur;
};
class StackWithMin1{
public:
StackWithMin1(){
}
~StackWithMin1(){
}
void push(int val){
s1.push(val);
if(val<=min())
s2.push(val);
}
void pop(){
if(s1.top()==min())
s2.pop();
s1.pop();
}
int top(){
return s1.top();
}
bool empty(){
return s1.empty();
}
int min(){
if(s2.empty()) return MAX_INT;
else return s2.top();
}
private:
stack s1, s2;
};
完整代码如下：
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
using namespace std;
const int MAX_INT = ~(1<<31);//2147483647
typedef struct node{
int val, min;
}node;
class StackWithMin{
public:
StackWithMin(int size=1000){
buf = new node[size];
buf[0].min = MAX_INT;
cur = 0;
}
~StackWithMin(){
delete[] buf;
}
void push(int val){
buf[++cur].val = val;
if(val<buf[cur-1].min) buf[cur].min = val;
else buf[cur].min = buf[cur-1].min;
}
void pop(){
--cur;
}
int top(){
return buf[cur].val;
}
bool empty(){
return cur==0;
}
int min(){
return buf[cur].min;
}
private:
node *buf;
int cur;
};
class stack{
public:
stack(int size=1000){
buf = new int[size];
cur = -1;
}
~stack(){
delete[] buf;
}
void push(int val){
buf[++cur] = val;
}
void pop(){
--cur;
}
int top(){
return buf[cur];
}
bool empty(){
return cur==-1;
}
private:
int *buf;
int cur;
};
class StackWithMin1{
public:
StackWithMin1(){
}
~StackWithMin1(){
}
void push(int val){
s1.push(val);
if(val<=min())
s2.push(val);
}
void pop(){
if(s1.top()==min())
s2.pop();
s1.pop();
}
int top(){
return s1.top();
}
bool empty(){
return s1.empty();
}
int min(){
if(s2.empty()) return MAX_INT;
else return s2.top();
}
private:
stack s1, s2;
};
int main(){
//cout<<MIN_INT<<endl;
StackWithMin1 mystack;//StackWithMin mystack;
for(int i=0; i<20; ++i)
mystack.push(i);
cout<<mystack.min()<<" "<<mystack.top()<<endl;
mystack.push(-100);
mystack.push(-100);
cout<<mystack.min()<<" "<<mystack.top()<<endl;
mystack.pop();
cout<<mystack.min()<<" "<<mystack.top()<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/12/19/3.2/
