问:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。时间复杂度为O(1)。
import java.util.Stack; public class Solution { //此栈保存元素 Stack<Integer> ele = new Stack<Integer>(); //此栈保存最小值 Stack<Integer> min = new Stack<Integer>(); //入栈,元素先保存,判断当前入栈的数据与栈中最小值相比较谁最小,如果当前的小,入栈min,否则不变 public void push(int node) { ele.push(node); if(min.isEmpty()){ min.push(node); }else{ if(min.peek()>node){ min.push(node); } } } //出栈,将出栈的元素放到一个变量中,判断是否是最小元素,如果是则将保存最小元素的栈中数据弹出 public void pop() { int topData = ele.peek(); ele.pop(); if(topData==this.min()){ min.pop(); } } //获取最小值,如果占中有数据,则是最小值,如果没有,则栈已经被弹空 public int min() { if(min.isEmpty()){ return Integer.MAX_VALUE; }else{ return min.peek(); } } }