首页 > 其他 > 详细

Leetcode Min Stack

时间:2015-10-10 06:46:12      阅读:134      评论:0      收藏:0      [点我收藏+]

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.

解题思路:

比较直观。用一个min stack专门存放最小值,如果有比它小或是相等的(有多个平行的最小值都要单独存放,否则pop后会出问题),

则存放其到minstack.


Java code:

class MinStack {
    Stack<Integer> elements = new Stack<Integer>();  
    Stack<Integer> minStack = new Stack<Integer>();  
      
    public void push(int x) {
       elements.push(x);
       if(minStack.isEmpty() || x <= minStack.peek()){
           minStack.push(x);
       }
    }

    public void pop() {
       if(elements.isEmpty()){
           return;
       }
       if((int)elements.peek() == (int)(minStack.peek())){
           minStack.pop();
       }
       elements.pop();
    }

    public int top() {
        return elements.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Reference:

1. http://www.cnblogs.com/yuzhangcmu/p/4106783.html

 

Leetcode Min Stack

原文:http://www.cnblogs.com/anne-vista/p/4865637.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!