思路(单调队列)
核心数据结构:维护一个下标的双端队列 dq,使得队列中对应的值严格单调递减。这样队首始终是当前窗口的最大值下标。
对每个下标 i 执行:
- 删除过期:如果 dq 的队首下标小于当前窗口的左边界(即 dq.front()≤i−k),就从队首弹出。
- 维护单调性:当 nums[dq.back()]≤nums[i] 时,从队尾弹出,直到队列对应值重新递减。
- 加入新元素:把 i 加到队尾。
题目内容
给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧,你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。