题目描述
设计一个支持 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.
算法1
(模拟) $O(n)$
比较直观的思路就是我们额外新增一个栈,栈顶存放当前元素的最小值。每当新元素入栈的时候,除了压入存放元素的栈外,我们也将最小值压入最小值栈中,这里最小值就是新元素与最小值栈栈顶的最小值。
C++ 代码
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
stack<int> stk1, stk2;
void push(int x) {
stk1.push(x);
if (stk2.empty()) stk2.push(x);
else stk2.push(min(stk2.top(), x));
}
void pop() {
stk1.pop();
stk2.pop();
}
int top() {
return stk1.top();
}
int getMin() {
return stk2.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
算法2
(模拟) $O(n)$
假如入栈的数是单调递增的,那么显然栈中的最小值一直都是最开始入栈的那个元素。所以如果一个元素比最小值大且后入栈,那么它其实是没有用的,即不会影响栈中的最小值。
因此最小值栈中只用压入比当前最小值小的元素。具体做法是只有当新元素小于或等于当前栈顶的时候才会入栈,而出栈时如果当前元素与最小值栈的栈顶相同,我们让最小值栈顶也出栈。
C++ 代码
class MinStack {
public:
/** initialize your data structure here. */
stack<int> stk, minStk;
MinStack() {
}
void push(int x) {
stk.push(x);
if (minStk.empty() || minStk.top() >= x) minStk.push(x);
}
void pop() {
int t = stk.top();
stk.pop();
if (minStk.top() == t) minStk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return minStk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
提示
以上两种算法也都可以用一个栈来实现,不过为了回溯到前一个最小值,我们在将最小值压栈时需要压入前一个最小值,然后另外用一个变量来记录当前的最小值。
算法3
(模拟) $O(n)$
如果只用一个栈来模拟,我们可以将最小值和当前元素都压入栈中,并且用一个变量来记录当前元素中的最小值。问题的难点在于当元素出栈时,如果出栈的是最小元素,我们应该怎样回溯到前一个最小值。这里采取的做法是入栈时将元素与当前最小值的差值插入栈中,并更新最小值。出栈时如果栈顶元素大于0,说明该元素入栈时比当时的最小值大,可以直接出栈,如果小于0说明该元素更新了最小值,我们需要在该元素出栈后回溯到前一个最小值,回溯的方法是让当前最小值与栈顶元素相减。这里因为会有溢出问题我们将元素以long long
形式存储。
C++ 代码
class MinStack {
public:
typedef long long LL;
stack<LL> stk;
LL min_value;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if (stk.empty()) min_value = x;
stk.push(x - min_value);
min_value = min((LL)x, min_value);
}
void pop() {
auto t = stk.top();
stk.pop();
if (t < 0) min_value -= t;
}
int top() {
auto t = stk.top();
if (t > 0) return min_value + t;
else return min_value;
}
int getMin() {
return min_value;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/