algorithm - 从现有数组构造一个数组

Question

给定一个整数数组A[1...n-1]whereN是数组 A 的长度。构造一个数组B，使得B[i] = min(A[i], A[i+1], ..., A[i+K-1]), whereK将被给出。数组 B 将有 N-K+1 个元素。

我们可以使用 min-heaps 为 k 个元素构造 min-heap - O(k) 来解决这个问题。对于每个下一个元素，删除第一个元素并插入新元素并堆化。

因此最坏情况时间 - O( (n-k+1)*k ) + O(k) 空间 - O(k)

我们能做得更好吗？

Answer 1

如果在 OP 的算法中我们将昂贵的“heapify”过程更改为更便宜的“upheap”或“downheap”，我们可以做得更好。这给出了 O(n * log(k)) 时间复杂度。

或者，如果我们遍历输入数组并将每个元素放入大小为“k”的最小队列，我们​​可以在 O(n) 时间内完成。Min-queue 是一个可以在 O(1) 时间内执行 find-min 的队列。它可以实现为一对最小堆栈。有关详细信息，请参阅此答案。