滑动窗口最值

10 分钟

求每个长度为 k 的窗口的最大值:用递减单调队列存下标。每步先从队尾弹出比新元素小的,再把新下标入队;然后从队头弹出滑出窗口的下标;此时队头即当前窗口最大值。整体 O(n)。

小纸条

求窗口“最大值”时,队列里元素应保持递增还是递减?

登录 后可看答案

滑动窗口最值 · 算法进阶 · op599 课程