滑動窗口最小算法

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)。