单调队列（单调双端队列）：一种在队列（通常用 deque 实现）中保持元素（或其对应值）单调递增/递减的技巧，用于在均摊 \(O(1)\) 时间内维护区间最值等信息，常见于滑动窗口最大/最小值与某些 DP 优化。
/ˈmɑːnətoʊn kjuː/
Use a monotone queue to get the maximum in each sliding window.
用单调队列来求每个滑动窗口里的最大值。
By maintaining indices in a decreasing monotone queue, we can update the window maximum in amortized \(O(1)\) time as the window moves.
通过在递减单调队列中维护下标，窗口移动时就能以均摊 \(O(1)\) 的时间更新窗口最大值。
monotone 来自希腊语词根 mono-（“单一”）+ tonos（“音调/张力”），引申为“单调的、单一方向变化的”。queue 来自法语 queue（“尾巴、队列”）。组合成 monotone queue，在算法语境中指“队列内部保持单调性”的数据结构技巧（通常用双端队列实现）。
Select Language