微信面试题，信面试题,遇到这道算法题，当时被卡

微信面试题，信面试题,遇到这道算法题，当时被卡

遇到这道算法题，当时被卡住，故今天把它写出来做下知识整理，

原题：实现一个栈，满足min() pop() push()方法的时间复杂度都为O(1).( min()返回栈中最小元素)

思路1：用一个变量minItem记录栈中的最小值，在push()中每次加入一个item就跟minItem对比，item更小，只item赋给minItem，然后再min() 中直接return minItem;

这种思路没考虑在pop()过程中，对minItem的影响，当栈顶元素是minItem，执行pop()后minItem就不知道指向谁了，因为栈只记录最小值而起，至于最小值之前那些大小关系都没记录

正确思路：为了实现更低的时间复杂度，我们都会想到用空间去换时间，所有这里增加一个数组来nextMinItem[index] 元素大小关系。如果当前最小值是对象 item1 当push进来的item2比 item1更小，且元素个数从原本的a增加到a+1这时候我们用我们就应该把item2这个更小的item赋给minItem 然后用nextMinItem[a+1] = item1 来记录 item2后面的次小值，这样一来当item2 这个栈顶被pop()掉的话，我们就可以minItem = nextMinItem[a+1]，来恢复minItem。

public class Stack {    private int itemCount = 0;    private Item minItem = null;    private Item[] nextMinItem;    private Item stackTop = null;    private int maxSize = 100;    public Stack() {        nextMinItem = new Item[maxSize];    }    class Item {        int Data;        Item nextItem;        public Item(int data) {            this.Data = data;        }     }    public boolean push(Item item) {        if (itemCount == maxSize) {            System.out.println("栈已满");            return false;        }        itemCount++;        if (minItem == null) {            minItem = item;        } else {            if (item.Data < minItem.Data) {                nextMinItem[itemCount] = minItem;                minItem = item;            }        }        item.nextItem = stackTop;        stackTop = item;        return true;    }    public boolean pop() {        if (itemCount == 0) {            System.out.println("栈是空的，无法出栈");            return false;        }         if (stackTop == minItem) {            minItem = nextMinItem[itemCount];        }        stackTop = stackTop.nextItem;        itemCount--;        return true;    }    public Item min() {        if (itemCount == 0) {            System.out.println("栈是空的，无最小值");            return null;        }        return minItem;    }    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        Stack stack = new Stack();        stack.push(stack.new Item(5));        System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.push(stack.new Item(4));        System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.push(stack.new Item(3));        System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.push(stack.new Item(2));        System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.push(stack.new Item(1));        System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.pop();        System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.pop();        System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.pop();        System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.pop();        System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);        stack.pop();        System.out.println("栈结构为：n|____1_____|n|____2_____|n|____3_____|n|____4_____|n|____5_____|n");             }}//该片段来自于http://byrx.net