滑动窗口最大值
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)。
英文解析
Approach: Maintain a decreasing deque of indices. Remove smaller values from the back when a new value enters, remove expired indices from the front, and the front is always the maximum of the current window.
Complexity: Time , space .