如何用单调双端队列实现 O(n) 查询滑动窗口最大值索引的原理？

问题背景与常见痛点

在实际项目中。往往需要在一个不断移动的窗口里实时获取最大值的索引。很多同学在实现时会遇到以下困惑：

• 窗口大小不固定：传统的暴力遍历每次都要重新扫描窗口，导致 O 的时间开销。
• 难以同时维护“最大值”和“窗口边界”：既要把已经离开窗口的元素剔除，又要保证队首始终是当前最大值。
• 代码实现繁琐、易出错：手动维护两个指针、数组或链表会产生大量下标越界和重复元素残留的问题。
• 性能瓶颈：O 根本无法接受。

这些痛点正是我们引入单调双端队列的动机——它能一次遍历数组，即可在 O 时间内完成所有窗口的最大值索引查询。

单调双端队列的主要思想

单调双端队列是一种特殊的双端队列，它内部保存的是数组元素的索引而且这些索引对应的数值始终保持严格递减 的顺序。其实，

• # 队头 : 当前窗口内最大的元素索引。
• # 队尾 : 可能成为将来最大值的候选者。