你会得到一个整数流

Question

你会得到一个整数流和一个 window 大小的整数 k，你只会一个接一个地收到流整数。每当你收到一个整数时，你必须 return 包括当前条目在内的最后 k 个整数中的最大数。

面试官期望 O(N) 时间 + O(1) 平均案例 space N 个任务的复杂性解决方案并且数组中没有给出整数，每次只有一个整数作为输入传递给你的方法。

我尝试解决它但无法提出 O(N) 解决方案。谁能告诉我我们该怎么做。

Answer 1

这是想到的答案（C++）

#include <iostream>
#include <limits>
using namespace std;

int main()
{
    cout << "Enter K: " << endl;
    int K;
    cin >> K;

    cout << "Enter stream." << endl;

    int n, counter = 1, max = std::numeric_limits<int>::min();
    while (cin >> n){
        if (counter % K == 0)
           max = std::numeric_limits<int>::min();
        if (n > max) 
           max = n;
        cout << max << endl;
        ++counter;
    }
}

Answer 2

O(N)时间容易，但O(1)平均space不可能。

这是我们绝对需要存储的内容。对于我们在最后 k 个输入中看到的任何数字 x，如果我们从 x 开始看到更大的数字，我们可以忘记 x，因为我们永远不需要return 它或再次将它与任何东西进行比较。如果自 x 以来我们还没有看到更大的数字，我们需要存储 x，因为我们可能不得不在某个时候 return 它。因此，我们需要存储最后 k 项中最大的数，然后是最大的，然后是最大的，一直到当前输入。在最坏的情况下，输入是递减的，我们总是需要存储所有最后 k 个输入。在一般情况下，在任何时候，我们都需要跟踪 O(log(k)) 项；但是，峰值内存使用量将大于此值。

我们使用的算法是简单地跟踪我们刚才说我们需要存储的所有数字的双端队列，按照它们的自然降序，以及我们看到它们的时间*。当我们收到一个输入时，我们从双端队列的右侧弹出低于它的所有内容，并将输入压入双端队列的右侧。我们向左看，如果我们看到左边的项目比 window 尺寸旧，我们向左弹出。最后，我们向左看，我们看到的数字是滑动window最大值。

该算法在摊销常数时间内处理每个输入。处理输入的唯一部分不是恒定时间是我们可能弹出所有双端队列的部分，但是由于每个输入在算法过程中只弹出一次，所以它仍然是摊销常数。因此，该算法需要 O(N) 时间来处理所有输入。

*如果 N 大得离谱，我们可以跟踪我们看到事物的索引 mod k 以避免溢出问题。

Answer 3

首先，大多数面试官会认为内存O(k)是O(1)。

考虑到这些细节，您可以只实现一个环形缓冲区：

int numbers[k]; // O(1) because k is constant
int i = 0, next_number;
while (next_number= new_number()) {
    numbers[i % k]= next_number;
    i++;
    if (i >= k) {
        int max= MIN_INT;
        for (int j= 0; j < k; j++) { // O(1) because k is constant
            if (numbers[j] > max) max = numbers[j];
        }
        yield(max);
    }
}

当然，如果他们不认为 O(k) 是 O(1)，那么问题就没有解决方案，他们要么搞砸了他们的问题，要么希望你说这个问题是错了。

这里 fifo/deque 通常更快（对于大于某个数字的 k），我只是在演示一个愚蠢问题的最简单答案。

Answer 4

假设k很小并且不是缩放参数N的一部分（问题说N是任务，但不太清楚那是什么意思）。

实现一个 FIFO，插入和删除在时间上花费 O(1)，在内存中花费 O(k)。
同时实现一个 max 变量
弹出最旧的值，看它是否等于 max，如果是（这不太可能对 max 的所有值），则运行超过 k FIFO 的元素重新计算max，否则不计算。摊销后，这是 O(1).
将新值与 max 进行比较，并在必要时更新 max。
将 max 推入 FIFO。

那么时间是O(1)，内存是O(k+1)。我不明白你怎么没有存储要求至少 O(k)。处理 N 个整数的时间是 O(N).

你会得到一个整数流

You will be given a stream of integers

algorithm

asymptotic-complexity