algorithm - 获取 "friend"塔的编号

Question

给定编号为 1、2、3、...、n 的 n 塔及其高度(h[i] = towers[i] 的高度)和一个数字k。

两座塔a，b被认为是 friend 当且仅当:

• a - b = k
• h[a] == h[b]
• 最大(h[a+1], h[a+2] ... h[b - 1]) <= h[a]

有多少“友谊”？

解决方案很简单:

for i = 1, 2, 3, 4, 5, ..., n - k:
    if h[i] == h[i+k]:
        for j in range[i, i+k] :
             MAX = max(MAX, h[j]
        if MAX <= h[i]:
             ans++

但我想要以最有效的方式解决问题。请帮忙。

对于较大的n，程序会占用内存；为了减少它，我使用队列而不是数组来添加塔的高度(当 q.size() == k, Just q.pop() )。使用天真的解决方案检查具有大 k 的第三个条件必须花费时间。

Answer 1

可以使用deque来提供O(n)的算法。
在每一步:

Remove too old elements from the deque head  
       (if currentindex - index >= k)  
Remove elements from tail that have no chance to become maximum 
       in the k-size window (those < currentvalue)  
Add new element (index) to the deque tail  

这将 k 大小窗口中的最大元素的索引保留在双端队列的头部，因此您可以确定 - 两个塔之间是否有更大的值

用伪代码描述(滑动最小值)算法: Can min/max of moving window achieve in O(N)?