面试金典--min栈的实现

题目描述：实现一个包含min操作的栈，时间复杂度需要是O(1)

思路：一开始的想法是添加辅助栈保存当前最小元素，但是这样存在的问题就是不能处理重复元素；于是.....我还是google了，找到如下锦囊妙计

不需要额外的空间，栈顶保存的是最小元素，每次push比较，如果当前元素更小的话就更新栈顶，另外栈顶以下元素保存的是元素push的时候与

当时的最小值的差值；pop的时候，就是看栈顶元素后的下一个元素，如果小于零，说明当前需要pop最小元素，同时更新最小元素，如果大于零，

直接push（最小元素+差值）即可。有点混乱：

看例子：

3 5 2 1

push:

2 3

2 -1 2

2 -1 -1 1

pop:

2 -1 2 输出1

2 3 输出2

3 输出5

输出3

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 using namespace std;
15 
16 template<typename T>
17 class minStack
18 {
19 public:
20     T pop();
21     void push(const T& elem);
22     T min();
23     stack<T> s;
24 };
25 template<typename T>
26 void minStack<T>::push(const T&elem)
27 {
28     if(s.empty())
29     {
30         s.push(elem);
31         return;
32     }
33     T minval = s.top();
34     s.pop();
35     s.push(elem-minval);
36     if(elem < minval)
37     {
38         s.push(elem);
39     }
40     else
41         s.push(minval);
42     return;
43 }
44 
45 template<typename T>
46 T minStack<T>::pop()
47 {
48     if(s.empty())
49         throw std::out_of_range("stack is empty");
50     T minval = s.top();
51     s.pop();
52     T val = s.top();
53     s.pop();
54     if(val <= 0)
55     {
56         s.push(minval - val);
57         val = minval;
58     }
59     else
60     {
61         s.push(minval);
62         val = minval+val;
63     }
64     return val;
65 }
66 
67 int main()
68 {
69     return 0;
70 }

面试金典--min栈的实现

相关推荐