155. 最小栈
描述
- 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素x推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路
- 题目要求MinStack兼顾Stack和最小队列两种容器的特性，因此可以利用一个Stack加一个Vector来共同存储每个元素。利用空间换时间，保证常数时间的getMin操作。
- Vector的插入需要移动元素，比较耗时，因此可以将其改为一个Stack，负责按顺序存储当前最小元素。
- 值得注意的是，当栈顶元素出栈时，不会存在比栈顶元素大，比次栈顶元素小的元素还在栈内。如3,1,2依次入栈。当1出栈时，2已经早早就出栈了。
class MinStack_155_01 {
public:
MinStack() {}
void push(int x) {
s.push(x);
auto iter = vec.begin();
while (iter != vec.end()) {
if (*iter > x) break;
++iter;
}
vec.insert(iter, x);
}
void pop() {
int tmp = s.top();
s.pop();
auto iter = vec.begin();
while (iter != vec.end()) {
if (*iter == tmp) break;
++iter;
}
if (iter != vec.end()) vec.erase(iter);
}
int top() { return s.top(); }
int getMin() { return vec.front(); }
private:
vector<int> vec;
stack<int> s;
};
class MinStack_155_02 {
private:
stack<int> s, ms;
public:
MinStack() {}
void push(int x) {
if (ms.empty() || x <= ms.top()) ms.push(x); // 注意这里是<=
s.push(x);
}
void pop() {
int tmp = s.top();
s.pop();
if (tmp == ms.top()) ms.pop();
}
int top() { return s.top(); }
int getMin() { return ms.top(); }
};
