【LeetCode-困难题】239. 滑动窗口最大值

题目

方法一：单调双端队列

  if(deque.peekFirst() == nums[i - k])  deque.removeFirst();
1

1. 这一步很关键，当队首元素（最大元素）是滑动窗口后要被抛弃的元素时，他就不能再是最大值了，就必须去掉，
2. 如果队首元素（最大元素）不是滑动窗口被抛弃的元素，则继续充当最大值（队首元素）

解题步骤：

1. 构建双端对列

2. 构建窗口，如果当前待入队元素大于队列尾部元素，则将尾部元素弹出 直到当前待入栈元素不大于队尾元素 或者队列为空 才能加入队列
   

3. 开始滑动：当队首元素（最大元素）是滑动窗口后要被抛弃的元素时，他就不能再是最大值了，就必须去掉，接着如果当前待入栈元素大于队列尾部元素，则将尾部元素弹出 只到当前待入队元素不大于队尾元素 或者队列为空 才能加入队列
   

4. 在处理的同时将队首的窗口最大元素加入结果集

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k==1) return nums;
        int[] res = new int[nums.length  -  k  +1];  //实现计算最后结果集的大小
        Deque<Integer>  deque = new LinkedList<>(); //双端队列   实现   单调队列
        //未形成窗口  --需要形成窗口
        for(int i = 0 ; i <k  ;  i++){
            //如果当前待入队元素大于队列尾部元素，则将尾部元素弹出  直到当前待入栈元素不大于队尾元素  或者队列为空 才能加入队列
            while(!deque.isEmpty() && nums[i] > deque.peekLast())   deque.removeLast();
            deque.addLast(nums[i]);//将当前元素入队
        }
        res[0] = deque.peekFirst();//获取第一个k位置的最大值
        int j = 1;
        for(int i = k ; i<nums.length; i++ ){
            //当队首元素（最大元素）是滑动窗口后要被抛弃的元素时，他就不能再是最大值了，就必须去掉，
            if(deque.peekFirst() == nums[i - k])  deque.removeFirst();
            //如果当前待入栈元素大于队列尾部元素，则将尾部元素弹出  只到当前待入栈元素不大于队尾元素  或者队列为空
             while(!deque.isEmpty() && nums[i] > deque.peekLast())
                  deque.removeLast();
            deque.addLast(nums[i]);//将当前元素入队
            res[j++] = deque.peekFirst();//获取第一个k位置的最大值

        }
         return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27