给定一个由N个元素组成A[0 .. N - 1]的数组,则产生一个数组B,使得:
B[i] = min (A[i], A[i+1], ..., A[i+K-1]).
Run Code Online (Sandbox Code Playgroud)
(数组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}
Run Code Online (Sandbox Code Playgroud)
要解决该问题,可以使用其中push_rear(),pop_front()和get_min()都是固定时间操作的队列。
k将数组中的第一个元素推送A到此队列。然后继续从数组中填充队列A,同时从中弹出元素并将最小值添加到数组中B。
时间复杂度为O(N)。空间复杂度是O(k)。