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

可以考虑与当前stack维护对应的代表stack对应位置的最大值的栈MaxStack

对于栈stack

push元素 valueA时
           maxValue = popMaxStack();  pushMaxStack(maxValue);

           if  (valueA >= maxValue)   pushStack(valueA) ; pushMaxStack(valueA);
           if  (valueA < maxValue)    pushStack(valueA) ; pushMaxStack(maxValue);

pop元素
           maxValue = popMaxStack();  pushMaxStack(maxValue);
           valueA = popStack();
           popMaxStack();


这样取最大值时，直接  maxValue = popMaxStack();pushMaxStack(maxValue);就ok了。

我的实现是



import java.util.ArrayList;
import java.util.EmptyStackException;
import java.lang.NullPointerException;

public class StackForPriorImpl<E extends Comparable<E>> implements
IStackForPrior<E> {

private int numberOfObject;
private ArrayList<E> dataForOrginal;
private ArrayList<E> dataForMaximun;
private ArrayList<E> dataForMinimun;
private E maxElement;
private E minElement;

public StackForPriorImpl(){
this.numberOfObject = 0;
this.dataForOrginal = new ArrayList<E>();
this.dataForMaximun = new ArrayList<E>();
this.dataForMinimun = new ArrayList<E>();
}

@Override
public void push(E e) {

if(e==null){
throw new NullPointerException();
}

dataForOrginal.add(e);

if(numberOfObject==0){
maxElement = e;
minElement = e;
this.dataForMaximun.add(maxElement);
this.dataForMinimun.add(minElement);
}else{

if(e.compareTo(maxElement)>0){
dataForMaximun.add(e);
maxElement = e;
}else{
dataForMaximun.add(maxElement);
}

if(e.compareTo(minElement)<0){
dataForMinimun.add(e);
minElement = e;
}else{
dataForMinimun.add(minElement);
}
}

++numberOfObject;

}

@Override
public E pop() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = --numberOfObject;

dataForMaximun.remove(index);
maxElement = dataForMaximun.get(index-1);

dataForMinimun.remove(index);
minElement = dataForMinimun.get(index-1);

E e = dataForOrginal.get(index);
dataForOrginal.remove(index);
return e;
}

@Override
public E peekMedian() {

if(numberOfObject==0){
throw new EmptyStackException();
}

Object[] elementArray=this.dataForOrginal.toArray();
int lengthOfElementArray = elementArray.length;
quickSort(elementArray,0,lengthOfElementArray-1);

return (E)elementArray[lengthOfElementArray/2];
}

@Override
public E peekMaximum() {

if(numberOfObject==0){
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMaximun.get(index);
}

@Override
public E peekMinimum() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMinimun.get(index);
}

@Override
public int size() {

return this.numberOfObject;
}

private static <E> void quickSort(E[] elementArray,int low,int high){
if(low<high){
int q = partition(elementArray,low,high);
quickSort(elementArray,low,q-1);
quickSort(elementArray,q+1,high);
}
}

private static <E> int partition(E[] elementArray,int low,int high){
int i = low, j=high+1;
E e= elementArray[low];
while(true){
while(elementArray[++i].toString().compareTo(e.toString())<0 && i<high);
while(elementArray[--j].toString().compareTo(e.toString())>0);
if(i>=j) break;

E temp = elementArray[i];
elementArray[i]=elementArray[j];
elementArray[j]=temp;
}

elementArray[low] = elementArray[j];
elementArray[j]=e;

return j;
}

public static void main(String[] args){
StackForPriorImpl<Integer> stack=new StackForPriorImpl<Integer>();

stack.push(new Integer(2));
stack.push(new Integer(1));
stack.push(new Integer(2));
stack.push(new Integer(2));
stack.push(new Integer(6));
stack.push(new Integer(4));
stack.push(new Integer(2));
stack.push(new Integer(5));

System.out.println("size = "+stack.size());
System.out.println("peekMaximun = "+stack.peekMaximum().toString());
System.out.println("peekMinimun = "+stack.peekMinimum().toString());
System.out.println("peekMedian = "+stack.peekMedian().toString());

}
}

写得很好~~
跟我当时的做法是一样的.