LeetCode

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int[] a = new int[length-k+1];
        int[] q = new int[length];
        int hh=0,tt=-1;
        for(int i = 0 ; i < nums.length;i++){
            //判断队头是否划出窗口 i-k+1表示的是
            if(hh<=tt && q[hh] < i-k+1) hh++;
            //保持队列单调递减 如果当前值大于队尾，则剔出队尾的值，
            while(hh<=tt && nums[i] > nums[q[tt]]) tt--;
            //新元素插入到队尾
            q[++tt] = i;
            //赋值
            if(i>=k-1) a[i-k+1] = nums[q[hh]];
        }
        return a;
    }
}

核心
维护单调队列

代码解析
if(hh<=tt && q[hh] < i-k+1) hh++;

while(hh<=tt && nums[i] > nums[q[tt]]) tt–;

q[++tt] = i;