AcWing 41. 包含min函数的栈(仅使用一个栈)
原题链接
简单
作者:
wzc1995
,
2019-12-03 01:29:38
,
阅读 28
算法
(栈) $O(n)$
- 两个栈的方法已经烂大街了,这里提供仅用一个栈的方法。
- 我们只开一个普通栈和一个变量
min_value
记录最小值。栈中存放当前元素与当前最小值的差值。
- 进栈时,如果栈为空,则插入当前元素,然后更新
min_value
。如果栈不空,则插入 x - min_value
,然后更新 min_value
。
- 出栈时,如果栈顶元素小于 0,则说明栈顶元素为当前最小值,需要回滚上一次的最小值。出栈。
- 取栈顶元素时,如果栈中只有一个元素,直接返回。否则,如果栈顶元素大于 0,则说明栈顶不是当前最小值,通过差值计算找到最小值;如果栈顶元素小于 0,则直接返回最小值。
- 返回最小值时,直接返回
min_value
。
- 注意,整数运算有可能溢出,需要用
long long
。
时间复杂度
空间复杂度
C++ 代码
class MinStack {
public:
/** initialize your data structure here. */
#define LL long long
stack<LL> st;
LL min_value;
MinStack() {
}
void push(int x) {
if (st.empty()) {
st.push(x);
min_value = x;
} else {
st.push(x - min_value);
min_value = min(min_value, (LL)(x));
}
}
void pop() {
if (st.top() < 0)
min_value -= st.top();
st.pop();
}
int top() {
if (st.size() == 1)
return st.top();
else if (st.top() > 0)
return min_value + st.top();
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();
*/