这是一个作业问题。设A[]为整数数组,K为整数--窗口大小。生成数组M,其中包含在滑动A时看到的最小值。我找到了一篇文章,其中提供了解决此问题的方法,但我不理解它为什么具有O(n)复杂度。是否有人可以向我解释一下?
这是一个作业问题。设A[]为整数数组,K为整数--窗口大小。生成数组M,其中包含在滑动A时看到的最小值。我找到了一篇文章,其中提供了解决此问题的方法,但我不理解它为什么具有O(n)复杂度。是否有人可以向我解释一下?
O(N^2)
的时间,因为你推理出添加需要 O(N)
的时间,而你有 O(N)
个元素。然而,请注意每个元素只能添加一次和删除一次。因此,在总体上,要滑过整个数组 A
,需要 O(N)
的时间。O(1)
。换句话说,移动滑动窗口一个元素的平均时间是 O(1)
。