题解 | 滑动窗口的最大值(腾讯二面）

import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || size <= 0 || size > num.length)
            return res; // 处理边界情况

        Deque<Integer> deque = new ArrayDeque<>(); // 存储索引的双端队列

        for (int i = 0; i < num.length; i++) {
            // 1. 移除超出窗口范围的队头元素，用i-size+1 到 i 来维持双端队列的范围，
            while (!deque.isEmpty() && deque.peekFirst() < i - size + 1) {
                deque.pollFirst();
            }

            // 2. 维护队列单调递减：从队尾移除小于当前值的元素
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }

            // 3. 当前索引入队
            deque.offerLast(i);

            // 4. 当窗口形成后，记录当前窗口最大值
            if (i >= size - 1) {
                res.add(num[deque.peekFirst()]); // 队头即最大值
            }
        }
        return res;
    }
}

当时腾讯csig二面考过，我写的双指针法+单调队列， 面试官一直追问还有什么方法，当时没答出来。 今天重新做这道题，用一个单调递减的双端队列来维持滑动窗口，最后返回的头元素就是滑动窗口的最大值。 首先分两部 1. 就是移除窗口内的左侧元素（过期元素因为要往右移动遍历） 用 (i-size +1, i) 这个区间来维护，2.移动比较 最小的元素，从队尾移除所有小于当前元素的索引（因为它们不可能是后续窗口的最大值）， 之后，当前元素入队， 再将 窗口内的 头元素（最大值）加入 new的 arraylist中，返回res