java O(/)时间复杂度O(n)

ki0zmccv 于 2022-12-25 发布在 Java

关注(0)|答案(4)|浏览(240)

我感兴趣的是创建一个类似于堆栈的Java数据结构，它尽可能高效地支持以下操作：

Push，它在堆栈顶部添加一个新元素，
Pop，移除堆栈的顶部元素，
Find-Max，返回（但不移除）堆栈中最大的元素，以及
Find-Min，返回（但不删除）堆栈中最小的元素，以及

这个数据结构的最快实现是什么？我该如何用Java来写它？

Java

来源：https://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-on

4条答案

按热度按时间

8e2ybdfx1#

这是一个经典的数据结构问题。问题背后的直觉如下-最大值和最小值可以改变的唯一方式是将新值推入堆栈或将新值弹出堆栈。鉴于此，假设在堆栈中的每一级，您都跟踪堆栈中该点或其以下的最大值和最小值。然后，当你把一个新元素压入堆栈时，你可以很容易地（在O（1）时间内）通过比较刚刚压入的新元素和当前的最大值和最小值来计算栈中任意位置的最大值和最小值.类似地，当你弹出一个元素时，你将暴露栈顶以下一步的元素，其已经具有与其并排存储的堆栈的其余部分中的最大值和最小值。
直观地说，假设我们有一个堆栈，并按顺序将值2、7、1、8、3和9相加，我们从压入2开始，因此我们将2压入堆栈，由于2现在也是堆栈中最大和最小的值，我们记录如下：

2  (max 2, min 2)

现在，让我们推7。由于7大于2（当前最大值），我们得到以下结果：

7  (max 7, min 2)
 2  (max 2, min 2)

请注意，现在我们可以通过查看堆栈顶部来读取堆栈的最大值和最小值，看到7是最大值，2是最小值。如果现在压入1，则得到
在这里，我们知道1是最小值，因为我们可以将1与存储在堆栈顶部的缓存最小值（2）进行比较。作为练习，请确保您理解为什么将8、3和9相加后会得到以下结果：

9  (max 9, min 1)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

现在，如果我们想要查询max和min，我们可以在O（1）中通过阅读堆栈顶部存储的max和min（分别为9和1）来完成。
现在，假设我们弹出顶部的元素，得到9并将堆栈修改为

3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

现在请注意，这些元素的最大值是8，这正是正确的答案！如果我们接着按0，我们会得到：

0  (max 8, min 0)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

如您所见，最大值和最小值计算正确。
总的来说，这会导致堆栈的实现具有O（1）push、pop、find-max和find-min，这是渐进的最好结果。我将把实现作为练习。：-）但是，您可能需要考虑使用标准堆栈实现技术之一来实现堆栈，例如使用dynamic array或linked list对象，其中每个对象都保存堆栈元素min和max。您可以通过利用ArrayList或LinkedList来轻松实现这一点。或者，您可以使用提供的Java Stack类，尽管IIRC由于同步而导致一些开销，这些开销对于此应用程序来说可能是不必要的。
有趣的是，一旦你用这些属性构建了一个堆栈，你就可以用它作为构建块来构建一个具有相同属性和时间保证的队列，你也可以用它来构建一个具有这些属性的双端队列。

**编辑：如果您感兴趣，我的个人站点上有a min-stack和前面提到的min-queue**的C++实现。希望这能展示出实际操作中的效果！

赞(0）回复(0）举报 2022-12-25

nbnkbykc2#

虽然answer是对的，但是我们可以做得更好，如果栈有很多元素，那么我们浪费了很多空间，但是我们可以通过以下方法保存这些无用的空间：
我们可以使用两个堆栈来代替每个元素的最小值（或最大值），因为最小值（或最大值）的变化不会那么频繁，所以只有当新值是<=（或>=）时，我们才将最小值（或最大值）压入相应的堆栈。
下面是Java中的实现：

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

请注意，使用这种方法，minStack和maxStack中的元素将非常少，从而节省了空间。

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)

赞(0）回复(0）举报 2022-12-25

4c8rllxm3#

可能来不及回复，但只是为了记录。以下是java代码。

import java.util.ArrayList;
import java.util.List;

public class MinStack {
    List<Node> items;

    public void push(int num) {
        if (items == null) {
            items = new ArrayList<Node>();
        }
        Node node = new Node(num);
        if (items.size() > 0) {
            node.min = Math.min(items.get(items.size() - 1).min, num);
            node.max = Math.max(items.get(items.size() - 1).max, num);

        } else {
            node.min = num;
            node.max = num;
        }
        items.add(node);
        printStack();
    }

    public Node pop() {
        Node popThis = null;
        if (items != null && items.size() > 0) {
            popThis = this.items.get(items.size() - 1);
            items.remove(items.size() - 1);         
        }
        printStack();
        return popThis;
    }

    public int getMin() {
        if (items != null && items.size() > 0) {
            int min = this.items.get(items.size() - 1).min;
            System.out.println("Minimum Element > " + min);
            return min;
        }
        return -1;
    }

    public int getMax() {
        if (items != null && items.size() > 0) {
            int max = this.items.get(items.size() - 1).max;
            System.out.println("Maximum Element > " + max);
            return max;
        }
        return -1;
    }

    public void printStack() {
        int i = 0;
        for (Node n : items) {
            System.out.print(n.data + " > ");
            if (i == items.size() - 1) {
                System.out.print(" | Min = " + n.min + " |");
                System.out.print(" | Max = " + n.max + " |");

            }
            i++;
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MinStack stack = new MinStack();
        stack.push(10);

        stack.push(13);
        stack.push(19);
        stack.push(3);
        stack.push(2);
        stack.push(2);
        stack.printStack();
        stack.pop();
        //stack.getMin();
        stack.printStack();

    }
}

堆栈类：

class Node {

        int data;
        int min;
        int max;

        public Node(int data) {
            super();
            this.data = data;
        }

        public Node() {
            super();
        }
    }

赞(0）回复(0）举报 2022-12-25

cedebl8k4#

使用链接列表：

public class MaxMinStack {
    MaxMinLLNode headMin = null;
    MaxMinLLNode headMax = null;
    MaxMinLLNode tailMin = null;
    MaxMinLLNode tailMax = null;

    public void push(int data) {
        MaxMinLLNode node = new MaxMinLLNode(data, null);
        if (headMin == null) {
            headMin = node;
            tailMin = node;
        } else {
            if (data < headMin.data) {
                tailMin = headMin;
                headMin = node;
                node.nextNodeReference = tailMin;
            }
        }

        if (headMax == null) {
            headMax = node;
            tailMax = node;
        } else {
            if (data > headMax.data) {
                tailMax = headMax;
                headMax = node;
                node.nextNodeReference = tailMax;
            }
        }

    }

    public void pop() {
        System.out.println("Max Element:" + " " + String.valueOf(headMax.data));
        System.out.println("Min Element:" + " " + String.valueOf(headMin.data));
    }

    public void traverse() {
        MaxMinLLNode ptrMin = headMin;
        MaxMinLLNode ptrMax = headMax;
        System.out.println("Min");
        while (ptrMin != null) {
            System.out.println(ptrMin.data);
            ptrMin = ptrMin.nextNodeReference;
        }

        System.out.println("Max");
        while (ptrMax != null) {
            System.out.println(ptrMax.data);
            ptrMax = ptrMax.nextNodeReference;
        }

    }

    public static void main(String[] args) {
        MaxMinStack m = new MaxMinStack();
         m.push(7);
         m.push(4);
         m.push(5);
         m.push(6);
         m.push(7);
         m.push(8);
         m.push(1);
         m.push(1);
         m.push(7);
         m.push(2);
         m.push(4);
         m.push(2);
         m.traverse();
         m.pop();
    }

}

class MaxMinLLNode {
    int data;
    MaxMinLLNode nextNodeReference;

    MaxMinLLNode(int data, MaxMinLLNode node) {
        this.data = data;
        this.nextNodeReference = node;
    }
}

赞(0）回复(0）举报 2022-12-25

我来回答

java O(/)时间复杂度O(n)

4条答案

相关问题

热门标签

最新问答