本文为剑指 offer 系列第二十二篇。
主要知识点为栈，要求给栈再pop和push操作之外在添加一个min操作来获得当前栈元素的最小值。
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））
解题思路
思路1
如果不考虑时间复杂度O(1)限制的话，我们可以加一个栈，然后加一个数组来存，每次找最小元素的话，可以利用stl的min_element来获的，在pop的时候记得将数组中的pop的元素也要删除掉。
但是这样复杂度会比较高。有一个查找和删除的操作。
思路2
用一个栈A来正常保存元素，另一个栈B来保存当前元素个数下A栈中最小的元素，两个栈始终保持同样高度。
- 进行pop操作的时候两个都pop。
- 进行push操作的时候，A正常push，Bpush的时候要判断新加入的元素和之前B的栈顶元素谁大谁小，push进去那个小的元素。
- 进行min操作的时候，返回B的栈顶元素即可。
解题代码
思路1代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
stack<int> mstack;
vector<int> mvec;
void push(int value) {
mstack.push(value);
mvec.push_back(value);
}
void pop() {
int a = mstack.top();
mstack.pop();
auto b = find(mvec.begin(),mvec.end(),a);
mvec.erase(b);
}
int top() {
return mstack.top();
}
int min() {
return *min_element(mvec.begin(),mvec.end());
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路2代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
//思路2 两个栈进行保存
stack<int> dstack;
stack<int> mstack;
void push(int value) {
dstack.push(value);
if(mstack.empty() || mstack.top()>value){
mstack.push(value);
}else{
mstack.push(mstack.top());
}
}
void pop() {
dstack.pop();
mstack.pop();
}
int top() {
return dstack.top();
}
int min() {
return mstack.top();
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！