百度一面算法题(常数时间内求栈中最大值)

链式存储 节点类

package test.stack;

public class Node <T extends Comparable> implements Comparable
{

	private T data;
	private Node<T> pre;
	private Node<T> post;
	
	public Node(T data)
	{
		this.data = data;
	}
	
	
	public void setPreviousNode(Node<T> node)
	{
		this.pre = node;
	}
	
	public void setPostNode(Node<T> node)
	{
		this.post = node;
	}
	
	public Node<T> getPreviousNode()
	{
		return pre;
	}
	
	public Node<T> getPostNode()
	{
		return post;
	}
	
	public T getData()
	{
		return this.data;
	}


	@Override
	public int compareTo(Object o) {
	
		Node<T> node = (Node<T>)o;	
		return this.getData().compareTo(node.getData());
	}
}

PSatack类

package test.stack;


import java.util.SortedSet;
import java.util.TreeSet;

public class PStack <T extends Comparable>
{

	private int size;
	private Node<T> head;
	private SortedSet<Node<T>> set = new TreeSet<Node<T>>();
	
	
	public T pop()
	{
		T data = null;
		if(head!=null)
		{
			this.set.remove(head);
			data = head.getData();
			head = head.getPostNode();
			head.setPreviousNode(null);	
			size--;
		}
		
		return data;
	}
	
	public T peek()
	{
		if(head!=null)
			return head.getData();
		return null;
	}
	
	public void push(T data)
	{
		Node node = new Node(data);
		set.add(node);
		if(head!=null)
		{
			node.setPostNode(head);
			head.setPreviousNode(node);
			head = node;
			
		}else
		{
			head = node;
		}
		size++;
	}
	
	public int size()
	{
		return this.size;
	}
	
	public T popMax()
	{
		if(head==null)
			return null;
		Node<T> max_node = set.last();
                  set.remove(max_node);
if(max_node.getPreviousNode()!=null)
		max_node.getPreviousNode().setPostNode(max_node.getPostNode());
		size--;
		return max_node.getData();
	}
}

o(1)是不可能的，push时可以通过比较当前值与前一个的最大值，当pop出最大值之后，可能有多个元素对应的最大值需要修改，因此popmax为o(1)不可能。

不知道题目的意思是peekmax还是popmax，如果是peekmax，那o(1)是可以的

package org.jf.alg;

/**
 *  * 算法描述：

一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。

设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。

可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。

 * @author junfeng.chen
 *
 */
public class Pstack<T extends Comparable> {

	private Node head;
	private int size ;
	
	public void push(T data)
	{
		Node node = new Node();
		node.data = data;
		
		if(head==null)
		{
			head = node;
			head.max = data;
		}else
		{
			
			if(head.max.compareTo(data)>0)
				node.max = head.max;
			else
				node.max = data;
			
			node.next = head;
			head = node;
		}
		size++;
	}
	
	
	public T pop()
	{
		if(head==null)
			throw new RuntimeException("Stack is empty");
		T data = head.data;
		if(size==1)
			head = null;
		else
			head = head.next;
		size --;
		return data;
	}
	
	public boolean isEmpty()
	{
		return size==0;
	}
	
	public int size()
	{
		return size;
	}
	public T peek()
	{
		if(size==0)
			return null;
		
		return head.data;
	}
	
	public T peekMax()
	{
		if(size == 0)
			return null;
		
		return head.max;
	}
	
	class Node
	{
		T data;
		T max;
		Node next;
		
	}
}