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

冷不防 2023-10-05 20:17 3阅读 0赞

#### 239. 滑动窗口最大值 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

返回滑动窗口中的最大值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

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

详细思路见书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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210224134447898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70