用给定的数组构造带约束的数组
给定一个由N个元素组成的数组A[0 .. N - 1]，生成一个数组B，使得：
B[i] = min (A[i], A[i+1], ..., A[i+K-1]). (数组B将恰好有(N-k+1)个元素。
时间复杂度应优于O(N*k)
我在考虑使用minheap...但是heapify会增加复杂度，而且蛮力也是O(n*k)
同样，空间复杂度s将小于等于O(k)
下面是一个例子
Input:
A={ 2,1,3,2,5,7,1}, N=7,k=3
Output:
B={1,1,2,2,1}
回答 4
Stack Overflow用户
发布于 2012-02-18 18:28:54
要解决这个问题，您可以使用queue in which push_rear(), pop_front() and get_min() are all constant time operations。
将数组A中的第一个k元素推送到此队列。然后继续从数组A填充队列，同时从中弹出元素并将最小值附加到数组B。
时间复杂度为O(N)。空间复杂度是O(k)。
Stack Overflow用户
发布于 2012-02-18 17:49:00
在O(N)而不是O(N*k)中执行此操作的关键是不为每个条目计算给定的公式B[i] = min (A[i], A[i+1], ..., A[i+K-1])，而是增量地更新它。
在每个步骤中，都有一个K排序条目的结果集。
第一步：从前K个条目计算B，并将结果赋给B[0]。
第一个增量步骤： Calculate B[1]您只需将A[i+K]添加到结果集中，并从结果集中减去A[0]，而不是重新添加K个条目。
对每个增量步骤进行更新：，因此对于每个额外的索引，您只有两次结果集的更新。
总体而言，你有线性复杂性。
Stack Overflow用户
发布于 2012-02-18 17:54:58
第一步
编写一个具有“递减键”特性的(最低优先级)队列。这意味着您可以转到一个节点(例如，通过指针)，减少它的值并更新堆(优先级队列)。
操作decrease_key将是O(log(k))，k是优先级队列中元素的数量。
第二步
请考虑以下操作：
Add A[i]：这包括将A[i]添加到优先级队列，以及在其中保留一个指针，例如指向在优先级队列中创建的节点的C[i]。这是O(log(k))Remove A[i]：这意味着转到包含A[i]的节点(通过C[i])，将其值减少到负无穷大，然后将其从堆的顶部删除。这也是O(log(k))
第三步
初始化优先级队列:将A的第一个k元素添加到优先级队列中。这是O(k*log(k))
第四步
像这样填充B的元素：
for i = 1 to n-k+1
B[i] = pQ.top
Remove A[i]
Add A[i+k]此部分为O(n*log(k))
最后分析
该算法的总时序为O(n*log(k))。空间顺序是O(k)。这是优先级队列的k节点，以及指向这些节点(数组C)的k指针，如果简单实施，这些节点将变为O(n)。
https://stackoverflow.com/questions/9343505
复制
腾讯云开发者
