设计一个支持 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.
详见: https://leetcode.com/problems/min-stack/description/
方法一:
- class MinStack {
- public:
- /** initialize your data structure here. */
- MinStack() {
- }
- void push(int x) {
- stk.push(x);
- if(sm.empty())
- {
- sm.push(x);
- }
- else if(sm.top()>=x)
- {
- sm.push(x);
- }
- }
- void pop() {
- int top=stk.top();
- stk.pop();
- if(top==sm.top())
- {
- sm.pop();
- }
- }
- int top() {
- return stk.top();
- }
- int getMin() {
- return sm.top();
- }
- private:
- stack<int> stk;
- stack<int> sm;
- };
- /**
- * 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();
- */
方法二:
- class MinStack {
- public:
- /** initialize your data structure here. */
- MinStack() {
- }
- void push(int x) {
- stk.push(x);
- if(sm.empty())
- {
- sm.push(x);
- }
- else if(sm.top()>=x)
- {
- sm.push(x);
- }
- else
- {
- sm.push(sm.top());
- }
- }
- void pop() {
- stk.pop();
- sm.pop();
- }
- int top() {
- return stk.top();
- }
- int getMin() {
- return sm.top();
- }
- private:
- stack<int> stk;
- stack<int> sm;
- };
- /**
- * 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();
- */
来源: http://www.bubuko.com/infodetail-2552093.html