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

百度一面算法题(常数时间内求栈中最大值)
算法描述：
一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。
设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。
可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。

我的maxNumList并没有存储所有数字啊，比如我按顺序入栈这些数字：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5, 9, 9]，然后我的maxNumList存入的数字是：[1, 5, 5, 7, 7, 8, 9, 9]； 

再然后我的栈连续POP两次以后变成：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5]， 

这时我的maxNumList也变成了[1, 5, 5, 7, 7, 8]， 

1、如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了,而且用多一个maxIndex存储最大值坐标。

2、做一链状列表； 

push的时候链表插入元素，并保持链表降序排列； 

pop的时候直接在链表种找到结点删除即可。 链表第一个结点始终为栈中元素最大值。

用第二种方法模拟实现：
 

package littlejava;

import java.util.LinkedList;

public class LinkedListMaxMinVal
{
    LinkedList stack = new LinkedList();//就是一个栈
    LinkedList linklist = new LinkedList();//当链表用

    /*add(int index, E element)
    Inserts the specified element at the specified position in this list.
    remove(int index)
    Removes the element at the specified position in this list.
    indexOf(Object o)
    Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
    */

    public void push(int x)
    {
        stack.push(x);
        int index=0,i;
        for(i=0;i
        {   //5 4 3 2 1
            if(x >=linklist.get(i))
            {
                index=i;
                break;
            }
        }
        if(i!=0 && i==linklist.size())
            linklist.add(i,x);//在最后加
        linklist.add(index, x);

    }
    public int pop()
    {
        int x=stack.getFirst();
        int index=linklist.indexOf(x);
        linklist.remove(index);
        return stack.pop();// Pops an element from the stack represented by this list.
    }

    public int getMax()
    {
        return linklist.getFirst();
    }

    public int getMin()
    {
        return linklist.getLast();
    }
    public int top()
    {
         /*取栈顶元素相当于取LinkedList容器的头位置的元素
          * Returns the first element in this list.
          **/
        return stack.getFirst();

    }

    public LinkedList getLinklist() {
        return linklist;
    }

    public LinkedList getStack() {
        return stack;
    }


    public static void main(String []args)
    {
        LinkedListMaxMinVal  mystack  = new LinkedListMaxMinVal();
        mystack.push(1);
        mystack.push(2);
        mystack.push(4);
        System.out.println(mystack.getMax());
        mystack.push(6);
        mystack.push(5);
        mystack.push(3);
        System.out.println(mystack.getMax());
        mystack.push(5);
        System.out.println(mystack.getMax());

        for(int i=0;i
        {
            System.out.print(+mystack.getLinklist().get(i)+" ");
        }

        mystack.pop();
        mystack.pop();
        mystack.pop();
        System.out.println();
        for(int i=0;i
        {
            System.out.print(+mystack.getLinklist().get(i)+" ");
        }
        mystack.push(8);
        System.out.println("\n"+mystack.getMax());
    }
}