[Leetcode] #155 Min Stack

Discription:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack.

Solution:

参考剑指offer：添加一个辅助栈保存最小元素，每次压入时，将之前的最小元素和新压入栈的元素两者的最小值保存到另一个辅助栈中。弹出时，数据栈和辅助栈同时弹出。

class MinStack { public: /** initialize your data structure here. */ stack<int> stack1; //数据栈 stack<int> stack2; //存放最小元素的栈 MinStack() { } void push(int x) { if(stack2.empty()){ stack1.push(x); stack2.push(x); }else{ int temp = stack2.top(); stack1.push(x); stack2.push(min(x,temp)); } } void pop() { stack1.pop(); stack2.pop(); } int top() { return stack1.top(); } int getMin() { return stack2.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(); */GitHub-Leetcode: https://github.com/wenwu313/LeetCode