使用链接列表构建最小最大堆栈

Question

>问题

这个想法是构造一个最小MAX堆栈，该堆栈可以在恒定时间内执行以下操作。

1. 推
2. 流行
3. 偷看
4. 获取最小值
5. 获取最大值

我的方法

我的想法是，我创建了一个节点结构，该结构将在插入时存储自己的值以及最小值和最大值。

因此，例如，当我将值 4 插入堆栈时，因为头部为空，节点会将最小值和最大值设置为自己的值。但是，如果头部在插入时不为空，那么我们会比较新节点值和头部最小值和最大值，例如，如果新节点值较小，则最小值将是它自己的值，否则它将采用头部的最小值。相同的逻辑应用于维护最小值和最大值。

因此，在任何给定时间，我们都可以偷看头部并获取给定时间堆栈的最小值和最大值。

法典

static class MinMaxStack {
Node head = null;
class Node{
Integer value;
Node next;
Integer min;
Integer max;
public Node(Integer val){
this.value = val;
}
}
public Integer peek() {
return head.value;
}
public Integer pop() {
Node temp = head;
if(head.next != null){
head = temp.next;
temp.next = null;
}else{
head = null;
}
return temp.value;
}

public void push(Integer number) {
Node x = new Node(number);
if(head == null){
head = x;
x.min = x.value;
x.max = x.value;
}else{
x.min = x.value < head.min ? x.value : head.min;
x.max = x.value > head.max ? x.max : head.max;
x.next = head;
head = x;
}
}

public Integer getMin() {
return head.min;
}

public Integer getMax() {
return head.max;
}
}

问题

我知道还有其他方法可以实现这一点，但我决定采用链接列表路线。由于某种原因，我的代码未能通过测试用例，所以我不确定我是否做错了什么。我只是想确保我的逻辑很好，因为我无法解决问题。

Answer 1

我可以看到两件事可以修复：

push：

在这一行中：x.max = x.value > head.max ? x.max : head.max;您正在将x.max重新分配给x.max，将其更改为：

x.max = x.value > head.max ? x.value : head.max;

pop：

您在这里需要的只是：

public Integer pop() throws EmptyStackException {
if (head == null) throw new EmptyStackException();
Integer result = head.value;
head = head.next;
return result;
}

本质上，您正在弹出head. 现在你可能想知道这是否会影响min，max。

不会的。有三种情况：

1. 弹出前的当前head可能是min值。
2. 弹出前的当前head可能是max值。
3. 1 和 2。

在所有情况下，如果删除head，则其下一个节点已包含下一个最佳min、max值，因为您在推送过程中更新它们。