您将获得一个整数流和一个表示窗口大小的整数 k，您将只会一个接一个地收到流整数。每当你收到一个整数时，你必须返回最后 k 个整数中的最大数，包括当前条目。
面试官期望 N 个任务的 O(N) 时间 + O(1) 平均案例空间复杂度解决方案，并且数组中没有给出整数，每次只有一个整数将作为输入传递给您的方法。
我尝试解决它但无法提出 O(N) 解决方案。谁能告诉我我们该怎么做。
最佳答案
假设 k 很小并且不是缩放参数 N 的一部分(问题说 N 是 Tasks，但不太清楚这意味着什么)。
- 实现 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)。
关于algorithm - 你会得到一个整数流，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31224494/