滑动窗口的最大值&队列的最大值

滑动窗口的最大值

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

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

示例:

输入: 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

方法一：暴力
每次都在滑动窗口中计算最大值

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] ans=new int[nums.length-k+1];
    for (int i = 0; i <= nums.length-k; i++) {
        int max=Integer.MIN_VALUE;
        for (int j = i; j < i+k; j++) {
            if(nums[j]>max){
                max=nums[j];
            }
        }
        ans[i]=max;
    }
    return ans;
}

时间复杂度O(nk)，空间复杂度O(n-k+1)

方法二：利用堆
将在滑动窗口中的元素放入堆中，堆顶为最大值

public int[] maxSlidingWindow(int[] nums, int k) {
    if(k==0){
        return new int[0];
    }
    int[] ans=new int[nums.length-k+1];
    PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
    for(int i=0;i<k-1;i++){
        queue.offer(nums[i]);
    }
    for(int i=0;i<nums.length-k+1;i++){
        queue.offer(nums[i+k-1]);
        ans[i]=queue.peek();
        queue.remove(nums[i]);//移除滑动窗口之外的元素
    }
    return ans;
}

时间复杂度O(nlogk)

方法三：双向队列
队列中的元素都在滑动窗口中，递减（可以重复）
在遍历过程中：

将不在窗口的元素从队列中移除
将队列中比当前元素小的移除
将当前元素添加到队列中
队首元素就是当前的最大值

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] ans = new int[nums.length - k + 1];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < k; i++) {
        clean(deque, nums[i], nums, i, k);
    }
    ans[0] = deque.getFirst();
    for (int i = k; i < nums.length; i++) {
        clean(deque, nums[i], nums, i, k);
        ans[i - k + 1] = deque.getFirst();
    }
    return ans;
}

public void clean(Deque<Integer> deque, int num, int[] nums, int cur, int k) {
    if (cur - k >= 0 && deque.getFirst() == nums[cur - k]) {//移除滑动窗口之外的元素
        deque.pollFirst();
    }
    while (!deque.isEmpty() && num>deque.getLast() ) {//移除比当前更小的元素
        deque.pollLast();
    }
    deque.addLast(num);
}

时间复杂度O(n)

新版本：
队首：小元素队尾：大元素

public int[] maxSlidingWindow(int[] nums, int k) {
    if (k == 0) {
        return new int[0];
    }
    int[] ans = new int[nums.length - k + 1];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < k - 1; i++) {
        removeSmaller(deque, nums[i]);
        deque.addFirst(nums[i]);
    }
    for (int i = 0; i < ans.length; i++) {
        int index = i + k - 1;
        removeSmaller(deque, nums[index]);
        deque.addFirst(nums[index]);
        removeOutQueue(deque, nums, k, index);
        ans[i] = deque.peekLast();
    }
    return ans;
}

public void removeSmaller(Deque<Integer> deque, int num) {
    while (!deque.isEmpty() && deque.getFirst() < num) {
        deque.pollFirst();
    }
}

public void removeOutQueue(Deque<Integer> deque, int[] nums, int k, int cur) {
    if (cur - k >= 0 && nums[cur - k] == deque.getLast()) {
        deque.pollLast();
    }
}

队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出:[null,null,null,2,1,2]

示例 2：

输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出:[null,-1,-1]

限制

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

使用辅助双端队列，队首存当前的最大值，整个队列递减

push(v)：从队尾移除所有小于当前的元素x（在移除v之前，必须移除了x，而在移除v之前，最大值不可能是x），再将当前元素添加到队尾
pop()：如果队首元素等于移除的元素，则移除队首元素

class MaxQueue {

    private Queue<Integer> queue = new LinkedList<>();

    private Deque<Integer> maxQueue = new LinkedList<>();

    public int max_value() {
        if (maxQueue.isEmpty()) {
            return -1;
        }
        return maxQueue.getFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!maxQueue.isEmpty() && value > maxQueue.getLast()) {
            maxQueue.pollLast();
        }
        maxQueue.offerLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        int value = queue.poll();
        if (maxQueue.getFirst() == value) {
            maxQueue.pollFirst();
        }
        return value;
    }
}