java - 使用链表构建最小最大堆栈

Question

问题

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

1. Push
2. Pop
3. Peek
4. getMinValue
5. getMaxValue

我的方法

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

因此，例如，当我将值 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

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

推送:

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

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

弹出:

这里你只需要:

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 值，因为您是在推送期间更新它们。