Crackingcodinginterview(3.2)堆栈实现常量复杂度的min函数

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. 1. Stack1，push(), pop()时间复杂度:O(n) 2.Stack2,与Stack3,满

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

1. Stack1，push(), pop()时间复杂度:O(n)

2.Stack2,与Stack3,满足要求，Stack3更优化，消除了部分冗余

3.堆栈特点，在当前元素为弹出时，当前元素的最小值不会改变

import java.util.Stack;

class Stack1{
	private Node top = null;
	private Node first = null;
	class Node{
		int val;
		Node next;
		Node min;
		public Node(int val){
			this.val = val;
			this.next = null;
			this.min = null;
		}
	}
	//time complexity:O(n) 
	public void push(int val){
		if(top != null){
			Node n = new Node(val);
			n.next = top;
			top  = n;

			if(first.val < val){
				//time complexity:O(n)
				Node p = null;
				for(p = first;;p = p.min)
					if(p.min == null || val < p.min.val){
						n.min = p.min;
						p.min = n;
						break;
					}
						
			}else{
				n.min = first;
				first = n;
			}
			
		}else{
			top = new Node(val);
			first = top;
		}
	}
	//time complexity:O(n) 
	public int pop(){
		if(top != null){
			Node n = top;
			top = top.next;
			
			Node p = null;
			if(!n.equals(first)){
				for(p = first;!n.equals(p.min);p = p.min)
					;
				p.min = p.min.min;
			}else{
				first = first.min;
			}					
			return n.val;
		}else{
			return Integer.MIN_VALUE;
		}
	}
	//time complexity:O(1)
	public int min(){
		if(first != null)
			return first.val;
		else
			return Integer.MAX_VALUE;
	}
	public boolean empty(){
		if(top == null)
			return true;
		else
			return false;
	}
}
class Stack2{
	private Node top;
	class Node{
		int val;
		int min;
		Node next;
		public Node(int val, int min){
			this.val = val;
			this.min = min;
			this.next = null;
		}
	}
	public void push(int val){
		if(top != null){
			Node n = new Node(val, val < top.min ? val : top.min);
			n.next = top;
			top = n;
		}else{
			top = new Node(val, val);
		}		
	}
	public int pop(){
		if(top != null){
			Node n = top;
			top = top.next;
			return n.val;
		}else{
			return Integer.MIN_VALUE;
		}
	}
	public int min(){
		if(top != null)
			return top.min;	
		else
			return Integer.MAX_VALUE;
	}
	public boolean empty(){
		if(top == null)
			return true;
		else
			return false;
	}
}
class Stack3{
	private Node top = null;
	private Stack s = new Stack();
	class Node{
		int val;
		Node next;
		public Node(int val){
			this.val = val;
			this.next = null;
		}
	}
	public void push(int val){
		if(top != null){
			Node n = new Node(val);
			n.next = top;
			top = n;
			
			if(s.peek() >= val)
				s.push(val);			
		}else{
			top = new Node(val);
			s.push(val);
		}
	}
	public int pop(){
		if(top != null){
			Node n = top;
			top = top.next;
			if(n.val == s.peek())
				s.pop();
			return n.val;
		}else
			return Integer.MIN_VALUE;
	
	}
	public int min(){
		if(top == null)
			return Integer.MAX_VALUE;
		else
			return s.peek();
	}
	public boolean empty(){
		if(top == null)
			return true;
		else
			return false;
	}
}
public class Solution{
	public static void main(String[] args){
		int[] A = {
			23, 11	, 12, 34, 10, 12, 7, 45, 21,
			12, 6, 12, 5, 85, 4, 3, 2, 1
		};
		//test for Stack1
		Stack1 stack1 = new Stack1();
		for(int i=0;i < A.length;i++){
			stack1.push(A[i]);
		}
		while(!stack1.empty()){
			System.out.print(stack1.pop() + "[" +
				stack1.min() + "]" + " ");
		}
		System.out.println();
		//test for Stack2
		Stack2 stack2 = new Stack2();
		for(int i=0;i < A.length;i++){
			stack2.push(A[i]);
		}
		while(!stack2.empty()){
			System.out.print(stack2.pop() + "[" +
				stack2.min() + "]" + " ");
		}
		System.out.println();
		//test for Stack3
		Stack3 stack3 = new Stack3();
		for(int i=0;i < A.length;i++){
			stack3.push(A[i]);
		}
		while(!stack3.empty()){
			System.out.print(stack3.pop() + "[" +
				stack3.min() + "]" + " ");
		}
		System.out.println();

	}
}