0

Given an unsorted array A with length N. How to maintain a sliding window with length D (D < N), such that when the sliding window slides from the start to the end of the array A, it can give out the current min of the window. The less the time complexity the better.Thx.

Luke
  • 135
  • 1
  • 2
  • 12
  • 1
    Regarding duplicate, finding maximum is nearly identical to finding minimum. – hatchet - done with SOverflow Jul 13 '18 at 20:38
  • If D is small, the runtime may be faster to do it with replacement/insertion sorting into an array rather than using the "optimal" dynamic programming approach. So, the actual implementation may want to use a threshold of when to switch techniques. – jxh Jul 13 '18 at 20:49
  • @Danny_ds: Recalculating the min is equivalent to insertion sort of new element after removal of an old element. Both will be O(D). – jxh Jul 13 '18 at 21:25

0 Answers0