title: Computing a moving maximum
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/12329073/find-the-min-number-in-all-contiguous-subarrays-of-size-l-of-a-array-of-size-n">Find the min number in all contiguous subarrays of size l of a array of size n</a>  </p>
  </blockquote>
  
  
  
  <p>I have a (large) array of numeric data (size <code>N</code>) and would like to compute an array of running maximums with a fixed window size <code>w</code>.</p>
  
  <p>More directly, I can define a new array <code>out[k-w+1] = max{data[k-w+1,...,k]}</code> for <code>k &gt;= w-1</code> (this assumes 0-based arrays, as in C++).</p>
  
  <p>Is there a better way to do this than <code>N log(w)</code>?</p>
  
  <p>[I'm hoping there should be a linear one in <code>N</code> without dependence on <code>w</code>, like for moving average, but cannot find it. For <code>N log(w)</code> I think there is a way to manage with a sorted data structure which will do <code>insert()</code>, <code>delete()</code> and <code>extract_max()</code> altogether in <code>log(w)</code> or less on a structure of size <code>w</code> -- like a sorted binary tree, for example].</p>
  
  <p>Thank you very much.</p>