滑动窗口

发表于 分类于 阅读次数：

无重复字符的最长子串[1005]

滑动窗口最大值[134]

思路：

  1. 固定窗口
  2. 单调递减队列（队列头到队列尾）来维护区间最大值

这是一个降本增笑的故事：

如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）

如果老员工 35 岁了，也裁掉。（元素离开窗口）

裁员后，资历最老（最左边）（队列头）的人就是最强的员工了。

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
28
29
30
31
32
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int l = 0, r = 0;
        List<Integer> res = new ArrayList<>();
        Deque<Integer> dq = new ArrayDeque<>(); // 单调队列，存下标，保持递减

        for (; r < nums.length; r++) {
            // 移除队尾比当前元素小的下标
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[r]) {
                dq.pollLast();
            }
            dq.offerLast(r);

            // 当窗口长度 >= k
            if (r - l + 1 < k) {
                continue; 
            }
            // 队头就是最大值
            res.add(nums[dq.peekFirst()]);

            // 移除队头已经滑出窗口的下标
            if (!dq.isEmpty() && dq.peekFirst() == l) {
                dq.pollFirst();
            }

            l++;
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }

}

最小覆盖子串[114]