滑动窗口最小值算法

Question

5

这是一个作业问题。设A[]为整数数组，K为整数--窗口大小。生成数组M，其中包含在滑动A时看到的最小值。我找到了一篇文章，其中提供了解决此问题的方法，但我不理解它为什么具有O(n)复杂度。是否有人可以向我解释一下？

- Michael

哦，不知道。在http://stackoverflow.com/questions/4114917/sql-query-for-vendors-who-have-sold-item-more-than-once上看到有人请求这个。也许标签描述中应该有一个注释？ - AndreKR

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JPvdMerwe · Accepted Answer

这往往会让人们感到困惑。你可能会认为它需要 O(N^2) 的时间，因为你推理出添加需要 O(N) 的时间，而你有 O(N) 个元素。然而，请注意每个元素只能添加一次和删除一次。因此，在总体上，要滑过整个数组 A，需要 O(N) 的时间。

这样可以获得摊销效率，即每次移动滑动窗口一个元素的平均效率为 O(1)。换句话说，移动滑动窗口一个元素的平均时间是 O(1)。