［算法］求栈中最小元素

如何用O(1)的时间复杂度求栈中最小元素

---

解题思路：

我们经常会采用空间换取时间提高时间复杂度。我们可以使用两个栈结构，一个栈用来存储数据，另一个栈用来存储栈中的最小元素。思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在出栈时，如果当前入栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为其入栈之前的那个最小值。

实现代码如下：

package 求栈中最小元素;
/**
 * 用链表方式实现栈
 * @author dream
 *
 * @param <E>
 */
public class MyStack<E> {

    Node<E> top = null;

public boolean isEmpty(){
return top == null;
    }

public void push(E data){
        Node<E> newNode = new Node<E>(data);
        newNode.next = top;
        top = newNode;
    }

public E pop(){
if(isEmpty()){
return null;
        }
        E data = top.data;
        top = top.next;
return data;
    }

public E peek(){
if(isEmpty()){
return null;
        }
return top.data;
    }
}

package 求栈中最小元素;

public class Node<E> {

    Node<E> next = null;
    E data;
public Node(E data){
this.data = data;
    }
}

package 求栈中最小元素;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;

public class MyStack1 {

    MyStack<Integer> elem;
    MyStack<Integer> min;

public MyStack1(){
        elem = new MyStack<>();
min = new MyStack<>();
    }

public void push(int data){
        elem.push(data);
if(min.isEmpty()){
min.push(data);
        }else{
if(data < min.peek()){
min.push(data);
            }
        }
    }

public int pop(){
        int topData = elem.peek();
        elem.pop();
if(topData == min()){
min.pop();
        }
return topData;
    }

public int min(){
if(min.isEmpty()){
return Integer.MAX_VALUE;
        }else {
return min.peek();
        }
    }

}