力扣hot100 滑动窗口最大值 单调队列
👨🏫 题目地址
🍻 AC code
class Solution {
public int[] maxSlidingWindow(int[] nums, int k)
{
int n = nums.length;
int[] res = new int[n - k + 1];
// 单调递减队列
int[] q = new int[n];// q数组维护的是元素在 nums 数组对应的下标
int h = 0, t = -1;
for (int i = 0; i < n; i++)// 枚举每一个窗口
{
if (h <= t && i - k + 1 > q[h])// 队头滑出窗口
h++;
while (h <= t && nums[q[t]] <= nums[i])// 处理新元素，维持队列单调递减
t--;
q[++t] = i;//新元素入队
if (i >= k - 1)//窗口大小达到k才记录答案
res[i - k + 1] = nums[q[h]];
}
return res;
}
}