《微软面试100题 In Java》02.Stack and minimum element in O(1)

题目： 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

分析：首先栈的push和pop时间复杂度都是O(1)的，但是对于min函数在没有排序的队列里一般时间复杂度是O(n).首先我想的是当我们push元素时我们定于一个临时的参数x，表示当前最小数，每次push元素时都进行比较更新，这样好像也能成功，但是当我们记录的元素被pop掉了呢，我们无从知道第二小的元素了，所以此时我们需要借助一个栈来记录下曾经保存下来的最小数。于是就有的第一种解法：

Solution 1: With Auxiliary Stack

class Node{
		public int item ;
		public Node next ;
		
		public int getValue(){ return item ;}
}
class MyStack{
	int N ; //size of myStack
	Node first ; // the top of stack
	
	
	//size of mystack
	public int size(){ return N ;}
	
	//empty or not
	public boolean isEmpty(){ return N==0 ;}
	
	
}
class MyStackMin{
	private MyStack stackData = new MyStack() ; //原stack
	private MyStack stackMin = new MyStack() ;	//辅助stack
	private int minNum ; //
	
	//push element to stack
	public void push(int newItem){
		//给新节点赋值
		Node newNode = new Node() ;
		newNode.item = newItem ;
		
		if(stackData.isEmpty()){
			stackData.first = newNode ;
			
			minNum = newItem ;     //the minNum
			Node minNode = new Node() ;
			minNode.item = minNum ;
			stackMin.first = minNode ;
			stackData.N++ ;
		}else{
			//给辅助stack push
			if(stackData.first.item>newItem){ minNum = newItem ;} //compare the push numble to the first
			Node minNode = new Node() ;
			minNode.item = minNum ;
			minNode.next = stackMin.first ;
			stackMin.first = minNode ;
			
			//push数据到原stack
			newNode.next = stackData.first ;
			stackData.first = newNode ;
			stackData.N++ ;
		}
	}
	
	//pop element from stack
	public void pop(){
		if(stackData.isEmpty()){
			System.out.println("error") ;
		}else{
			stackData.first = stackData.first.next ;
			
			stackMin.first = stackMin.first.next ;
		}
	}
	//search the min numble
	public int min(){
		return stackMin.first.getValue() ;
	}
}
public class StackMin{
	public static void main(String args[]){
		MyStackMin stack = new MyStackMin() ;
		stack.push(3) ;
		System.out.println(stack.min()) ;
		stack.push(4) ;
		System.out.println(stack.min()) ;
		stack.push(2) ;
		System.out.println(stack.min()) ;
		stack.push(1) ;
		System.out.println(stack.min()) ;
		stack.pop() ;
		System.out.println(stack.min()) ;
		stack.pop() ;
		System.out.println(stack.min()) ;
		stack.push(0) ;
		System.out.println(stack.min()) ;
	}
}

Solution 2: Without Auxiliary Stack

方案一我们是利用一个辅助stack来解决了当最小数被pop后无法寻找到第二小的数。那么不用辅助stack可以么，毕竟利用一个辅助浪费了空间和时间，当然可以，我们可以利用小小的改变来实现。就是存入栈中的数据时经过处理的。

Supposing that we are going to push a number value into a stack with minimum number min. Ifvalue is greater than or equal to the min, it is pushed directly into data stack. If it is less than min, we push 2*value -min, and update min as value since a new minimum number is pushed. How about to pop? We pop it directly if the top of data stack (it is denoted as top) is greater than or equal to min. Otherwise the number top is not the real pushed number. The real pushed number is stored is min. After the current minimum number is popped, we need to restore the previous minimum number, which is 2*min-top.

class MyStack{
	private int N ;
	private Node first ;
	private int minNum ;
	
	private class Node{
		private int item ;
		private Node next ;
		
		public int getItem(){ return item ;}
	}
	
	public boolean isEmpty(){ return N==0 ;}
	
	public void push(int newItem){
		Node newNode = new Node() ;
		
		if(isEmpty()){
			newNode.item = newItem ;
			minNum = newItem ;
			
			this.first = newNode ;
			N++ ;
		}else{
			if(newItem<minNum){
				newNode.item = 2*newItem -minNum ; //所经过的处理
				newNode.next = this.first ;
				this.first = newNode ;
				minNum = newItem ;
				N++ ;
			}else{
				newNode.item = newItem ;
				newNode.next = this.first ;
				this.first = newNode ;
				N++ ;
			}
		}
	}
	public void pop(){
		if(isEmpty()){
			System.out.println("error") ;
		}else{
			if(this.first.getItem()<minNum){
				minNum = 2*minNum-this.first.getItem() ;
			}
			this.first = this.first.next ;
		}
	}
	public int min(){
		return minNum ;
	}
}

public class StackMin2{
	public static void main(String args[]){
		MyStack stack = new MyStack() ;
		stack.push(3) ;
		System.out.println(stack.min()) ;
		stack.push(4) ;
		System.out.println(stack.min()) ;
		stack.push(2) ;
		System.out.println(stack.min()) ;
		stack.push(1) ;
		System.out.println(stack.min()) ;
		stack.pop() ;
		System.out.println(stack.min()) ;
		stack.pop() ;
		System.out.println(stack.min()) ;
		stack.push(0) ;
		System.out.println(stack.min()) ;
	}
}

Reference:

http://codercareer.blogspot.com/2011/09/no-02-stack-with-function-min.html

http://mydevelopedworld.wordpress.com/2012/10/17/solution-for-stack-and-minimum-element-in-o1/

《微软面试100题 In Java》02.Stack and minimum element in O(1),布布扣,bubuko.com

《微软面试100题 In Java》02.Stack and minimum element in O(1)

原文：http://blog.csdn.net/speedme/article/details/20716727