力扣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;}}