algorithm - 如何跟踪 fifo 查询的最大值/最小值

Question

我有 fifo 查询我在哪里放置和弹出 double 。每次更新后，我都需要最大值和最小值。我不需要查询中这些值的位置(或索引)。如何有效地做到这一点？ log(N) 甚至可能是 O(1)？

更新:找到这个Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

Answer 1

这是一个棘手的问题。请考虑以下事项:

假设你的 fifo 在任何给定时间的大小是 N。假设您仅使用一对 float 来跟踪最小值和最大值。假设 fifo 的大小保持合理不变。

因此我们可以假设队列上的一个“操作”在逻辑上由一次推送和一次弹出组成。

假设您正在比较两种处理方法:一种使用堆对，另一种使用简单的比较和搜索。

对于堆法:

每次操作，您都会推送到列表和两个堆，然后从列表和两个堆中弹出。堆操作总是O(log(n))，列表操作是O(1)，所以当N很大时，一个操作的时间复杂度是O(log(N))平均情况。重要的是要注意，无论当前弹出的元素是最小元素还是最大元素，堆操作总是如此复杂。因此，N 个操作的时间复杂度为 O(N*log(N))。

对于朴素的方法:

每次操作，您都会推送和弹出列表，并将弹出的项目与存储的最小值和最大值进行比较。如果该项目与其中任何一项相同，则您可以在列表中搜索具有相同值(value)的项目(在这种情况下，您会提前中断)，或者搜索整个列表的其余部分，直到找到下一个最佳元素。然后你用下一个最好的更新最小值/最大值。此方法具有 O(1) 典型情况和 O(N) 最坏情况(最小值或最大值需要更新)。重要的是要注意，对于 N 个数字的某些范围，您需要更新 min 和 max 的次数变为常数，而您不会变为 N 的次数。因此，N 操作的时间复杂度为在)。朴素的案例实际上比更高级的解决方案更好。

也就是说，我不认为堆可以有效地删除元素，所以你会遇到很多麻烦。

因此，考虑以下伪代码:

queue fifo;
float min, max;

void push(float f)
{
    if (fifo.size == 0)
    {
        min = f;
        max = f;
    }
    else if (f > max) max = f;
    else if (f < min) min = f;

    fifo.push(f);
}

float pop()
{
    if (fifo.size == 0) return (*((float *)NULL)); // explode
    float f = fifo.pop();
    if (fifo.size == 0)
    {
        min = NaN;
        max = NaN;
        return f;
    }
    if (f == max) search_max(fifo);
    if (f == min) search_min(fifo);
    return f;
}

search_max(queue q)
{
    float f = min;
    for (element in q)
    {
        if (element == max) return;
        if (element > f) f = element;
    }
    max = f;
}

search_min(queue q)
{
    float f = max;
    for (element in q)
    {
        if (element == min) return;
        if (element < f) f = element;
    }
    min = f;
}