滑动窗口最大值：从暴力超时到单调队列优化

刷算法题时，滑动窗口问题很常见，但LeetCode 239题“滑动窗口最大值”却让不少人卡壳。很多人第一反应是写两层循环，结果一提交就超时。这篇文章就来聊聊如何用单调队列轻松解决这道hard题。

题目是什么

题目本身不复杂：给定一个数组和一个窗口大小k，窗口每次向右滑动一格，要求返回每个窗口内的最大值。比如数组[1,3,-1,-3,5,3,6,7]，k=3时，窗口最大值依次是3,3,5,5,6,7。

暴力解法为什么超时

最直观的解法是两层循环：外层遍历窗口起始位置，内层遍历窗口内元素找最大值。时间复杂度是O(n*k)，当数组长度和k都很大时，效率极低，提交自然超时。

单调队列的优化思路

单调队列的核心思想是维护一个队列，队列中的元素按值递减排列，队首始终是当前窗口的最大值。具体做法是：

  1. 遍历数组，对于每个新元素，先移除队尾所有比它小的元素（因为它们不可能是后续窗口的最大值），然后将新元素入队。
  2. 同时，如果队首元素已经滑出窗口（索引小于窗口左边界），则将其出队。
  3. 这样，每个窗口的队首就是最大值。

由于每个元素最多入队和出队一次，总时间复杂度降为O(n)，空间复杂度为O(k)。

为什么值得关注

这道题是滑动窗口类问题的经典代表，单调队列的优化思路在很多场景中都有应用，比如求滑动窗口中的最小值、最大值，或者处理流式数据。掌握这种优化方法，能帮你解决一类看似复杂的问题。

如果你也曾在滑动窗口问题上栽过跟头，不妨试试单调队列，或许能让你“一遍过”。

参考来源