思路(单调队列)
核心数据结构:维护一个下标的双端队列 dq,使得队列中对应的值严格单调递减。这样队首始终是当前窗口的最大值下标。
对每个下标 i 执行:
- 删除过期:如果 dq 的队首下标小于当前窗口的左边界(即 dq.front()≤i−k),就从队首弹出。
- 维护单调性:当 nums[dq.back()]≤nums[i] 时,从队尾弹出,直到队列对应值重新递减。
- 加入新元素:把 i 加到队尾。
题目内容
给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧,你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值。
输入描述
第一行输入1个整数,分别为{n} 的个数,1<=nums.length<=105
第二行输入数列{n},用空格隔开,−104<=nums1<=104
第三行输入1个整数,滑窗长度,1<=k<=nums.length
输出描述
结果输出一行,数组每个滑窗的最大值
样例1
输入
8
1 3 -1 -3 5 3 6 7
3
输出
3 3 5 5 6 7