算法——单调队列

单调队列

什么是单调队列，想必大家对单调函数还有所印象，单调队列和单调函数类似，一个队列中的元素是递增或者递减的。

如何构建单调队列呢

并没有单调队列，那么如何构建呢，可以通过双端队列Deque 来进行构建。

注意事项

根据题意合适的选择 递增还是递减并过略掉一些不需要的元素。

leetcode239

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deq=new ArrayDeque<Integer>();
        int []res=new int[nums.length-k+1];
        int idx=0;
        for(int i=0;i<nums.length;i++){
            //因为要去除元素 所以记录的i
            while(!deq.isEmpty()&&deq.peek()<i-k+1){
                deq.pollFirst();
            }
            //因为头要弹出去 队列中剩下的比他小的也要弹出去 所以从后面开始 从前面开始可能会导致中间某个数大 从而不能保证每个头都是大的
            while(!deq.isEmpty()&&nums[deq.peekLast()]<nums[i]){
                deq.pollLast();
            }
            deq.addLast(i);

            if(i>=k-1){
               res[idx]=nums[deq.peek()];
               idx++;
            }
        }

        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

因为头要弹出去 队列中剩下的比他小的也要弹出去 所以从后面开始 从前面开始可能会导致中间某个数大 从而不能保证每个头都是大的
举例解释
假如数组为 [1,3,1,2,0,5]

判断头队列元素为

1
3
31
312
120 =>输出头为1 并不是最大的

判断尾队列元素为

1
3
31
32
20
5