题目描述
定义栈的数据结构, 请在该类型中实现一个能够得到栈中所含最小元素的 min 函数 (时间复杂度应为 O(1)).
利用两个栈, 一个栈来正常保存所有元素, 另一个栈作为辅助. 仅在以下情况使用:
push: 当辅助栈为空, 或者辅助栈顶元素大于入栈元素时, 辅助栈也 push(value)
pop: 当辅助栈顶元素等于主栈顶元素时, 辅助栈也 pop()
min: 返回辅助栈栈顶元素
- class Solution
- {
- public:
- stack<int> sta1;
- stack<int> sta2;
- void push(int value)
- {
- sta1.push(value);
- if (sta2.empty() || sta2.top()> value)
- sta2.push(value);
- }
- void pop()
- {
- if (sta2.top() == sta1.top())
- sta2.pop();
- sta1.pop();
- }
- int top()
- {
- return sta1.top();
- }
- int min()
- {
- return sta2.top();
- }
- };
[剑指 offer] 20. 包含 min 函数的栈
来源: http://www.bubuko.com/infodetail-2870359.html