移动窗口的最小值/最大值可以在 O(N) 中实现吗? [英] Can min/max of moving window achieve in O(N)?

问题描述

我有输入数组 A

 A[0], A[1], ... , A[N-1]

我想要返回 B 的函数 Max(T,A) 表示 A 上的最大值超过前一个大小为 T 的移动窗口

I want function Max(T,A) which return B represent max value on A over previous moving window of size T where

 B[i+T] = Max(A[i], A[i+T])

通过使用最大堆来跟踪当前移动窗口 A[i] 到 A[i+T] 上的最大值，该算法产生 O(N log(T)) 最坏情况.

By using max heap to keep track of max value on current moving windows A[i] to A[i+T], this algorithm yields O(N log(T)) worst case.

我想知道有没有更好的算法?也许是一个 O(N) 算法

I would like to know is there any better algorithm? Maybe an O(N) algorithm

推荐答案

O(N) 使用 Deque 数据结构是可能的.它保存对(值；索引).

O(N) is possible using Deque data structure. It holds pairs (Value; Index).

at every step:

  if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then 
     Deque.ExtractHead;
  //Head is too old, it is leaving the window

  while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do
     Deque.ExtractTail;
  //remove elements that have no chance to become minimum in the window

  Deque.AddTail(CurrentValue, CurrentIndex); 
  CurrentMin = Deque.Head.Value
  //Head value is minimum in the current window

这篇关于移动窗口的最小值/最大值可以在 O(N) 中实现吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！