30. 包含min函数的栈
1. 描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
2. 例子
示例 1:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.
3. 提示
- 各函数的调用总次数不超过 20000 次
4. 题解
各操作时间复杂度: O(1)
class MinStack
{
private:
stack<int> minValue;
stack<int> store;
public:
/** initialize your data structure here. */
MinStack()
{
}
// void push(int x)
void push(int num)
{
store.push(num);
if(minValue.empty() || num <= minValue.top())
minValue.push(num);
}
void pop()
{
if(store.empty()) return ;
int popValue = store.top();
store.pop();
if(minValue.top() == popValue)
minValue.pop();
}
int top()
{
return (store.empty() ? -1 : store.top()); // -1 should be a invalid value
}
int min()
{
return (minValue.empty() ? -1 : minValue.top()); // -1 should be a invalid value
}
};