239. 滑动窗口最大值

 窗口:是一种运动轨迹,一种运动策略
L,R:可以选择让L往右,或让R往右,但L不能越过R
3,2,1,5,6,5,6,7,2,3,7
0 1 2 3 4 5 6 7 8 9 10
L
R R R R
3 2 1 5
L
2 1 5
R

你可以根据你自己的策略让L或R往右动,但是不要违反L<=R
每一次做出选择,窗口都有一个数的状况,你怎么样能够做到任务一个状态下都能方便的得到最大值
你可以遍历,但是时间复杂度是O(N)

下面来看一下如何获得窗口的最大值和最小值:


3 2 1 5 6 5 6 7 2 2 7
0 1 2 3 4 5 6 7 8 9 10

用双端队列,队列放的是位置
如果是最大值,要保证位置所代表的值从左往右是严格减少
R往右动时,双端队列更新的过程
R
0 1 2
3 2 1
3
5
4 5
6 5
6
6
7 8
7 2
7 9
7 2
10
7
L
L 往右动时,检查队列头部是否是一个过期位置,如果则pop

这个流程的实质是什么?
这个双端队列代表:如果此时的窗口在L依次往右滑时,哪些位置会依次成为最大值


eg:
给定一个数组[3,2,1,5,6,5,6,7,2,3,7] w=3,统计每个窗口的最大值 n=11,w=3
3
queue
入队要严格单调递减
3 2 1 0 6 5 6 7 2 3 7
0 1 2 3 4 5 6 7 8 9 10
存储下标,信息更多
arr v: 3 2 1 0
queue i: 0 1 2 3
入队规则:
1、i 位置入队:如果队列不空,且arr[i]>=arr[queue.peekLast] .>>>> queue.poll
queue.addLast(i);
2、 如果队列位置过期出队
queue.peekFist==i-w 出队
3、 什么时候统计结果?窗口形成时:i>=w-1
结果集 int[] result=new int[11-3+1] n-w+1
当 i-w+1>=0 统计结果 result[index++]=arr[queue.peekFirst]

 public static int[] getMaxWindow(int[] arr,int w){
        //先排除无效参数
        if(arr==null||w<1||arr.length<w){
            return null;
        }

        //准备一个双队列,这里放的是位置
        LinkedList<Integer> queueMax=new LinkedList<>();
        //收集的结果 n=8,w=3 res.length=8-3+1
        int[] res=new int[arr.length-w+1];
        int index=0;
        //i->R
        //每一个i位置代表当前让i位置上面所代表的值进窗口,这个i就是R,让R往右动
        for(int i=0;i<arr.length;i++){

            //这时是R往右动时的策略
            //如果队列不为空且peekLast小于i位置的值,则出队
            while (!queueMax.isEmpty() && arr[queueMax.peekLast()]<=arr[i]){
                queueMax.pollLast();
            }
            //加入当前节点
            queueMax.addLast(i);

            //因为窗口大小是W,要维持窗口大小,所以i-w是过期的位置
            //eg: i=3,w=3,则过期位置是0,把0位置弹出
            //在一开始窗口还没有形成之前,是不会过期的
            // 一直是判断队列左边位置是否已过期
            if(arr[queueMax.peekFirst()]==i-w){
                queueMax.pollFirst();
            }

            //窗口形成好之后,收集结果 i=2,w=3,此时就一个有效的形成好的窗口,则i+1==w
            if(i>=w-1){
                res[index++]=arr[queueMax.peekFirst()];
            }
        }
        return res;
    }

  

239. 滑动窗口最大值

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

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

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:

输入:nums = [1], k = 1
输出:[1]
示例 3:

输入:nums = [1,-1], k = 1
输出:[1,-1]

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        
        LinkedList<Integer> queue=new LinkedList<>();
        int[] res=new int[nums.length-k+1];
        int index=0;
        for(int i=0;i<nums.length;i++){

            while(!queue.isEmpty()&& nums[queue.peekLast()]<=nums[i]){//双端队列里面放的是位置
                queue.pollLast();//弹出是poll
            }
            //queue放的是位置
            queue.add(i);

            //i=3,w=3 0
            //检查队头的位置是不是过期位置,如果是,则弹出
            if(queue.peekFirst()==i-k){
                queue.pollFirst();
            }

            //在窗口形成之后,收集结果,i=2,k=3,i+1==w
            if(i>=k-1){
                res[index++]=nums[queue.peekFirst()];
            }

        }
        return res;

    }
}

  

上一篇:leetcode 239 滑动窗口最大值


下一篇:239. 滑动窗口最大值(Hard)