定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示:
各函数的调用总次数不超过 20000 次
思路:定义一个辅助栈,最小的永远是栈顶,加入正常栈的时候维护这个辅助栈
加入:①如果辅助栈为空就直接加入||如果辅助栈顶元素大于现在要加入的元素就加入辅助栈②无论何时,A都是正常的栈,正常入栈出栈:如果正常出栈的元素是辅助栈的栈顶,辅助栈也d出min:辅助栈的栈顶就是最小的 知识点
peek与poop
Stack.peek() 返回栈顶元素。
Stack.pop() 返回栈顶元素,并在栈中删除它。
注意这里的代码的pop()处如果用"=="取代equals就会出错,这是因为:
- “==”两边都是包装类型时,会直接比较引用地址(IntegerCache除外);两边都是基本类型比较值;两边是不同类型就自动拆箱。equals不能比较基本类型,比较包装类型会先比较是否为同类型,之后比较值是否相同;参数为值类型会自动装箱成包装类型。JAVA的Integer有IntegerCache,他会缓存[-128-127]之间的对象,也就是说新创建的对象的值在[-128-127]之间会检查是否有已存在的[-128~127],如果有就直接调用,否则才会产生新对象。也就是说,如果连续新建两个相同值的Integer,如果值的大小在[-128~127],他们两个用"=="就是相等的,如果在这个范围之外,他们就不是同一个地址,就是不同的。
==和equals的不同:https://www.cnblogs.com/mrhgw/p/10449391.html
import java.util.Stack; class MinStack { StackA,B; public MinStack() { A=new Stack<>(); B=new Stack<>(); } //入栈 public void push(int x) { A.push(x);//A是正常栈,都正常加入 if (B.empty()||B.peek()>=x){//B是辅助栈,存储最小值 B.push(x); } } public void pop() { //如果当前最小值是B的栈顶,A和B栈都同时出栈 if (A.pop().equals(B.peek())){ B.pop(); } } public int top() { return A.peek(); } public int min() { return B.peek(); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)