algorithm - 滑动窗口最小算法

Question

这是一个家庭作业问题。令 A[] 是一个整数数组和整数 K——窗口大小。当它滑过 A 时，生成在窗口中看到的最小值数组 M。我找到了一篇文章，其中包含该问题的解决方案，但不明白为什么它具有 O(n) 复杂性。谁能给我解释一下？

Answer 1

这往往会把人赶出去。你会认为这需要O(N^2)时间，因为你认为添加需要O(N)时间并且你有O(N)元素。但是，实现每个元素只能添加一次和删除一次。因此，总共需要O(N)滑过整个阵列A。

这会产生O(1)每次将滑动窗口移动一个元素时的摊销效率。换句话说，滑动窗口移动一个元素所花费的平均时间是O(1)。