滑动窗口最大值

Sliding Window Maximum

问题：滑动窗口最大值

考察：数组、队列、滑动窗口

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/sliding-window-maximum

Problem: Sliding Window Maximum

Patterns: Array, Queue, Sliding Window

Recency: 3mo

Link: https://leetcode.com/problems/sliding-window-maximum

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：维护一个单调递减双端队列，队列中存下标。新元素进入时弹出所有不大于它的队尾元素，窗口左端越界时弹出队首；队首始终是当前窗口最大值。

复杂度：时间 O(n)，空间 O(k)。