定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
在看到这道题目的时候第一反应是要用一个最小值来保留当前栈中最小值,但是也能够很快地意识到比较麻烦的地方在于pop的时候怎么更新min值,看了别人的题解之后都是使用了另外一个栈来保持在入栈过程中曾经做过最小值的值,pop的时候判断两个栈顶元素是否一致,一致的话都要pop,在这种情况下取最小值需要从保存最小值的栈顶元素取值
另外一点是这道题目也顺便联系java中Stack的常用的方法empty(); push(); pop();peek();比较坑爹的时元素需要定义为static的并且要手动初始化,不然list会被初始化为null
我自己的想法是不希望用另外一个栈,那么为了实现这一目的,在栈中需要保留冗余的曾经的最小值,这样能够比较方便到找到当前的此小值,具体见下面的代码
import java.util.Stack; public class Solution { //需要这样写来初始化stack,不然会报空指针push的时候 private static Stack<Integer> stack = new Stack<Integer>(); private static Integer minElement