《剑指offer》—— 20. 包含min函数的栈（Java）

题目描述

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

import java.util.Stack;

public class Solution {
          
   

    
    public void push(int node) {
          
   
        
    }
    
    public void pop() {
          
   
        
    }
    
    public int top() {
          
   
        
    }
    
    public int min() {
          
   
        
    }
}

参考思路：

可以使用两个栈，一个 dataStack 栈存储数据，另一个 minStack 栈每次只存储当前最小值。

比如：依次插入的数据 ：8，6，5，5，7，9，3。

dataStack 中依次入栈： 8，6，5，5，7，9，3。

minStack 中依次入栈： 8，6，5，5，5，5，3。

如此之后，minStack 中的堆顶元素都是当前所有插入值中最小的。

参考实现：

import java.util.Stack;

public class Solution {
          
   
    //存储所有数据
    private Stack<Integer> dataStack = new Stack<>();
    //每次只存最小的数据
    private Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
          
   
        dataStack.push(node);
        //如果这个值比minStack中的所有值都小则插入，否则将minStack中现在最小的值(栈顶值)再插入一个。
        minStack.push(minStack.isEmpty() ? node : Math.min(node,minStack.peek()));
    }
    
    public void pop() {
          
   
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
          
   
        return dataStack.peek();
    }
    
    public int min() {
          
   
        return minStack.peek();
    }
}

附录：

Java Stack 类的相关方法

这里是猿兄，为你分享程序员的世界。