给定一个整数数组A[1...n-1]，其中N是数组A的长度。构造一个数组B 这样 B[i] = min(A[i], A[i+1], ..., A[i+K-1])，其中 K 会给出。数组 B 将有 N-K+1 个元素。
我们可以使用最小堆来解决问题 为 k 个元素构造最小堆 - O(k)。对于每个下一个元素，删除第一个元素并插入新元素并堆化。
Hence Worst Case Time - O( (n-k+1)*k ) + O(k) Space - O(k)
我们可以做得更好吗？
最佳答案
如果在 OP 的算法中我们将昂贵的“heapify”过程更改为更便宜的“upheap”或“downheap”，我们可以做得更好。这给出了 O(n * log(k)) 时间复杂度。
或者，如果我们遍历输入数组并将每个元素放入大小为“k”的最小队列，我们可以在 O(n) 时间内完成。 Min-queue 是一个可以在 O(1) 时间内执行 find-min 的队列。它可以实现为一对最小堆栈。参见 this answer了解详情。
关于algorithm - 从现有数组构造一个数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11159298/