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

问题描述

我输入数组A

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

我想函数MAX（T，A），其上的一个超过previous动码T窗口返回b重新present最大值，其中

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 [1]到A [I + T]，这种算法得到O（N日志（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），可以使用双端队列的数据结构。它拥有双（价值;指数）。

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屋！