双端队列实战 实现滑动窗口 用LinkedList的基类双端队列Deque实现 洛谷[P1886]

集合 关系 介绍

Deque 是一个接口

LinkedList 是这个接口的实现类

题目

输入输出

滑动窗口

基于双端队列实现

Deque<Integer> deque = new LinkedList<>();

滑动窗口代码

  public static List<Integer> maxSlidingWindow(int[] nums, int k) {List<Integer> result = new ArrayList<>();Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < nums.length; i++) {// 移除不在当前窗口的元素if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}// 移除队列中比当前元素小的元素，因为它们不可能成为最大值while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {deque.pollLast();}// 将当前元素的索引加入队列deque.offerLast(i);// 窗口已满，记录当前窗口的最大值if (i >= k - 1) {result.add(nums[deque.peekFirst()]);}}return result;}// 求每个窗口的最小值public static List<Integer> minSlidingWindow(int[] nums, int k) {List<Integer> result = new ArrayList<>();Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < nums.length; i++) {// 移除不在当前窗口的元素if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}// 移除队列中比当前元素大的元素，因为它们不可能成为最小值while (!deque.isEmpty() && nums[deque.peekLast()] >= nums[i]) {deque.pollLast();}// 将当前元素的索引加入队列deque.offerLast(i);// 窗口已满，记录当前窗口的最小值if (i >= k - 1) {result.add(nums[deque.peekFirst()]);}}return result;}