239. 滑动窗口最大值（数据结构系列）

239. 滑动窗口最大值

• 题目
• 解题思路
• 代码

题目

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

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

解题思路

这题关键是知道要用单调队列 来做，难点也是构造单调队列。
还有一个注意的点就是不一次性填满窗口，而是留一个不填，然后一填满就记录最大值，再删除队首的元素。

详细思路见书271

代码

class Solution {

        /*
        实现单调队列
        */
class MonotonicQueue{

        LinkedList<Integer> q=new LinkedList<>();
        /*在队尾添加元素*/
        public void push(int n){
            while(!q.isEmpty()&&q.getLast()<n){
                q.pollLast();
            }
            q.addLast(n);
        }
        /*返回当前队列中的最大值*/
        public int max(){
            return q.getFirst();
        }
        /*队头元素如果是n，删除它*/
        public void pop(int n){
            if(n==q.getFirst()){
                q.pollFirst();
            }
        }



}



    /*开始解题*/
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window=new MonotonicQueue();
        List<Integer> res=new ArrayList<>();

        for(int i=0;i<nums.length;i++){
            if(i<k-1){
                //先填满窗口的前k-1，留一个先不填
                window.push(nums[i]);
            }else{
                //扩大窗口到k
                window.push(nums[i]);
                //记录当前大小为k的窗口中的最大值
                res.add(window.max());
                //移除最左边的一个旧元素
                window.pop(nums[i-k+1]);
            }
        }
        //把res转成int[]
        int arr[]=new int[res.size()];
        for(int i=0;i<res.size();i++){
            arr[i]=res.get(i);
        }
        return arr;
    }
}