题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的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 类的相关方法

序号 方法描述
1 boolean empty() 测试堆栈是否为空。
2 Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3 Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4 Object push(Object element) 把项压入堆栈顶部。
5 int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

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

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话，
求点赞👍 求关注💗 求分享👬求评论📝
这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！