题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路

  1. 内部使用两个栈解题，一个栈用于正常的栈操作，另一个栈用于min相关操作。
  2. 当要push一个元素时，首先与min的栈顶元素比较，若小于，则将其压入min栈中，若大于，则min栈重复压入栈顶元素。
  3. 当要pop一个元素时，min栈和normal栈正常pop即可。
  4. 当要获取最小元素，直接弹出min栈的栈顶元素即可。

Java代码实现

import java.util.Stack;

public class Solution {

    private Stack<Integer> all = new Stack();

    private Stack<Integer> min = new Stack();

    public void push(int node) {
        if(min.isEmpty()){
            min.push(node);
        }else{
            if(min.peek()>node){
                min.push(node);
            }else{
                min.push(min.peek());
            }
        }
        all.push(node);
    }

    public void pop() {
        if(all.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        all.pop();
        min.pop();
    }

    public int top() {
        if(all.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        return all.peek();
    }

    public int min() {
        if(min.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        return min.peek();
    }
}