首页 > 代码库 > 155. Min Stack

155. Min Stack

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.

    Example:

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> Returns -3.
    minStack.pop();
    minStack.top();      --> Returns 0.
    minStack.getMin();   --> Returns -2.
  • 思路:可以用stack自己的函数实现push,pop,top这三个,关键就是getmin不好实现,那么需要另外一个minstack来存储小的数字。
    public class MinStack {
    
        /** initialize your data structure here. */
        
       	private Stack<Integer>stack;
    	private Stack<Integer>minStack;
    	public  MinStack() {
            stack=new Stack<>();
            minStack=new Stack<>();
        }
        
        public void push(int x) {//入栈
            stack.push(x);
            if(minStack.isEmpty()||x<=minStack.peek())//如果为空的或者是入栈的元素不大于栈顶元素均可入minstack。
            {
            	minStack.push(x);
            }
        }
        
        public void pop() {
           if(stack.peek().equals(minStack.peek()))
        	{
        		minStack.pop();//保证如果某个元素要出栈的时候,刚好在minstack里面,那么出栈。
        	}
            stack.pop();     
        }
        
        public int top() {
            return stack.peek();
        }
        
        public int getMin() {
        	return minStack.peek(); //因为minstack的栈顶元素永远都是当前栈中所有元素中的最小值,那么直接出栈顶元素即可。      
        }
    }
    

     

155. Min Stack