Min Stack

Leave a comment

November 20, 2016 by oneOokay

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来实现,如下:

public class MinStack {
 /** initialize your data structure here. */
 private Stack stack;
 private Stack minStack;
 public MinStack() {
 stack = new Stack();
 minStack = new Stack();
 }
 
 public void push(int x) {
 stack.push(x);
 if (minStack.isEmpty()){
 minStack.push(x);
 }else if (x <= minStack.peek()){
 minStack.push(x);
 }
 }
 
 public void pop() {
 if(stack.peek().equals(minStack.peek())){
 minStack.pop();
 }
 stack.pop();
 }
 
 public int top() {
 return stack.peek();
 }
 
 public int getMin() {
 return minStack.peek();
 }
}

/**
 * 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();
 */

第二种方法是直接用一个stack实现:
用了一个常数min和一个stack:

  • 当push x入stack: x <= min的时候,先push入旧的min,然后update 新的min值,再push入x;当x>min的时候,并不会改变当前的min,所以只push入当前值。
  • 当pop时:
    • 如果pop值等于当前的min,说明pop掉这个值会使当前min发生改变,同时也说明,这个值的下面一个值是push入该值之前的一个min。所以此时需要pop两次,第一次把正常的值pop掉,第二次,pop出的值赋给当前的min。它就是在还没有push入刚才pop掉那个数之前的min。存住这个min用来getMin用。
    • 如果当前值是大于min的,说明当push它入stack的时候并没有发生min的变化,我们只push进了这个值。所以现在只需要pop一次,并且min不变。
  • getMin就返回当前的min值
public class MinStack {

 /** initialize your data structure here. */
 private Stack<Integer> stack;
 private int min; //TODO: 这里我要是用Integer的话就跑不过,需要查一下int和Integer的区别
 public MinStack() {
 stack = new Stack<Integer>();
 min = Integer.MAX_VALUE;
 }
 
 public void push(int x) {
 if (x <= min){
 stack.push(min);
 min = x;
 }
 stack.push(x);
 }
 
 public void pop() {
 if (stack.pop() == min){
 min = stack.pop();
 }
 }
 
 public int top() {
 return stack.peek();
 }
 
 public int getMin() {
 return min;
 }
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: