單調隊列優化,雖說之前有 po 過類似的題目,但今天來講一下這個小東西好了。

單調對列優化 可以在 均攤 O(n) 取得一個序列中 所有固定長度區間(例如本題的 k) 中的極值,使用 Deque。

 

以最大值為例:

插入方法:

在插入一個元素前,先判斷隊列是否為空(head<=tail),然後再判斷隊尾元素是否比要插入的元素小(q[tail].val<data[insert]),如果是的話,則將隊尾元素刪除(--tail)。

重複以上過程,直至為空或隊尾元素比其大。

刪除方法:

這個要根據具體題目而定。在本題是如果當前的INDEX與隊首的INDEX相差大於等於K,則刪除。...轉載(懶的自己打xD)


單調對列優化 也有一些擴展,像是 DP。

我的code

http://codepad.org/r6ruAuhL

p.s: 語法要選 c++,g++ TLE 超久= =。

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()