《剑指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 类的相关方法

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

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

点个关注，不再迷路

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

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

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