滑动窗口最小算法

Question

这是一个家庭作业问题。让A []是一个整数和整数K窗口大小的数组。当它在A上滑动时生成在窗口中看到的最小值的数组M.我发现an article具有针对此问题的解决方案，但不明白为什么它具有O（n）复杂性。有人可以向我解释吗？

Answer 1

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

每当您将滑动窗口移动一个元素时，这会产生一个分摊效率O(1)。换句话说，将滑动窗口移动一个元素所需的平均时间为O(1)。