Cracking coding interview(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  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