我正在阅读 CTCI 书,发现这个答案令人困惑。目标是创建一个堆栈数据结构,可以在 O(1) 时间内压入、弹出和 min(获取堆栈中的最小元素)。我编写了一个具有两个堆栈的类,一个用于保存最小值,另一个用作常规堆栈。代码如下。据我所知,这在测试中是有效的。
public static class StackWithMin extends Stack<Integer>{
Stack<Integer> stack;
Stack<Integer> minStack;
public StackWithMin(){
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int value){
if(value <= min()){
minStack.push(value);
}
stack.push(value);
}
public Integer pop(){
int value = stack.pop();
if(value == min()){
minStack.pop();
}
return value;
}
public int min(){
if(minStack.isEmpty()){
return Integer.MAX_VALUE;
}
return minStack.peek();
}
}
但是,书中给出的答案我并不完全清楚。我学过两门 Java 类(class),但最后两门类(class)是 C 语言,所以我的 OOP 概念有点生疏。该类中只有一个堆栈字段,并使用 super 调用来更新“常规”堆栈,并使用 s2 调用来更新最小堆栈。在 Java 可视化工具中查看这一点,只显示一个堆栈对象,该对象显然存储着两个不同的堆栈。这个实现有效,但我不确定到底为什么。如果能得到澄清,我们将不胜感激!
public class Q2 /* MinStack */ extends Stack<Integer> {
private Stack<Integer> min = new Stack<Integer>();
public void push(int item) {
if (min.isEmpty() || item < min()) {
min.push(item);
}
super.push(item);
}
public Integer pop() {
int item = super.pop();
if (item == min()) {
min.pop();
}
return item;
}
public Integer min() {
return min.peek();
}
最佳答案
这段代码确实生成了两个堆栈。事实是Q2
类(class)扩展Stack<Integer>
class 表示存在于父类中的所有内容都存在于 Q2
中类,包括“常规”堆栈,但只是为了在 Java 中访问它,您需要使用 super
关键字。
此图可以解释包含父类的 OOP 概念(“Bird”中存在的所有内容都存在“AngryBird”中):
现在自从你的Q2
类“包括”一个堆栈并像堆栈一样运行,您正在为类中的成员创建一个新的第二个堆栈以获取最小值。
如果您想知道解决方案中的“错误”是什么,即您实际上没有使用基类,那么即使没有extends Stack<Integer>
,您的代码也可以工作。声明。
关于java - minStack 子类使用一个对象作为最小堆栈和常规堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51005581/