Java 双端队列实战 实现滑动窗口 用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;}

API

在 Java 中，Deque 是一个双端队列接口，它继承自 Queue 接口，支持在队列的两端进行元素的插入、删除和访问操作。LinkedList 是 Deque 接口的一个实现类，下面介绍 Deque<Integer> deque = new LinkedList<>(); 常见的操作。

1. 插入元素

• 在队列头部插入元素

• • addFirst(E e)：将指定元素插入此双端队列的开头。如果插入失败（例如队列已满，但 LinkedList 一般不会出现这种情况），会抛出异常。
  • offerFirst(E e)：将指定元素插入此双端队列的开头。如果插入成功返回 true，否则返回 false。

• 在队列尾部插入元素

• • addLast(E e)：将指定元素插入此双端队列的末尾。如果插入失败，会抛出异常。
  • offerLast(E e)：将指定元素插入此双端队列的末尾。如果插入成功返回 true，否则返回 false。

示例代码：

import java.util.Deque;  
import java.util.LinkedList;  public class DequeInsertionExample { public static void main(String[] args) { Deque<Integer> deque = new LinkedList<>(); // 在头部插入元素 deque.addFirst(1);  deque.offerFirst(2);  // 在尾部插入元素 deque.addLast(3);  deque.offerLast(4);  System.out.println(deque);  // 输出: [2, 1, 3, 4] } 
}

2. 删除元素

• 删除队列头部元素

• • removeFirst()：移除并返回此双端队列的第一个元素。如果队列为空，会抛出异常。
  • pollFirst()：移除并返回此双端队列的第一个元素。如果队列为空，返回 null。

• 删除队列尾部元素

• • removeLast()：移除并返回此双端队列的最后一个元素。如果队列为空，会抛出异常。
  • pollLast()：移除并返回此双端队列的最后一个元素。如果队列为空，返回 null。

示例代码：

import java.util.Deque;  
import java.util.LinkedList;  public class DequeRemovalExample { public static void main(String[] args) { Deque<Integer> deque = new LinkedList<>(); deque.add(1);  deque.add(2);  deque.add(3);  // 删除头部元素 Integer firstRemoved = deque.removeFirst();  System.out.println("Removed  first: " + firstRemoved); // 输出: Removed first: 1 // 删除尾部元素 Integer lastRemoved = deque.pollLast();  System.out.println("Removed  last: " + lastRemoved); // 输出: Removed last: 3 System.out.println(deque);  // 输出: [2] } 
}

3. 访问元素

• 访问队列头部元素

• • getFirst()：返回此双端队列的第一个元素。如果队列为空，会抛出异常。
  • peekFirst()：返回此双端队列的第一个元素。如果队列为空，返回 null。

• 访问队列尾部元素

• • getLast()：返回此双端队列的最后一个元素。如果队列为空，会抛出异常。
  • peekLast()：返回此双端队列的最后一个元素。如果队列为空，返回 null。

示例代码：

import java.util.Deque;  
import java.util.LinkedList;  public class DequeAccessExample { public static void main(String[] args) { Deque<Integer> deque = new LinkedList<>(); deque.add(1);  deque.add(2);  deque.add(3);  // 访问头部元素 Integer firstElement = deque.getFirst();  System.out.println("First  element: " + firstElement); // 输出: First element: 1 // 访问尾部元素 Integer lastElement = deque.peekLast();  System.out.println("Last  element: " + lastElement); // 输出: Last element: 3 } 
}

4. 其他操作

• isEmpty()：判断双端队列是否为空。
• size()：返回双端队列中的元素个数。

示例代码：

import java.util.Deque;  
import java.util.LinkedList;  public class DequeOtherOperationsExample { public static void main(String[] args) { Deque<Integer> deque = new LinkedList<>(); System.out.println("Is  deque empty? " + deque.isEmpty());  // 输出: Is deque empty? true deque.add(1);  deque.add(2);  System.out.println("Size  of deque: " + deque.size());  // 输出: Size of deque: 2 } 
}

例题

https://codeforces.com/problemset/problem/977/D

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);static int n;static long arr[];static boolean visited[];static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();/*** @throws IOException*/private static void solve() throws IOException {// todon=sc.nextInt();arr=new long[n];long max=0;ArrayList<Long>list=new ArrayList<>();for(int i=0;i<n;i++){arr[i]=sc.nextLong();list.add(arr[i]);max=Math.max(max,arr[i]);}Deque<Long> deque = new LinkedList<>();deque.add(max);long ans1=max;while(true){if(ans1%3==0){if(list.contains(ans1/3)){deque.addLast(ans1/3);list.remove(ans1/3);ans1/=3;continue;}}if(list.contains(ans1*2)){deque.addLast(ans1*2);list.remove(ans1*2);ans1*=2;continue;}break;}ans1=max;while(true){if(ans1%2==0){if(list.contains(ans1/2)){deque.addFirst(ans1/2);list.remove(ans1/2);ans1/=2;continue;}}if(list.contains(ans1*3)){deque.addFirst(ans1*3);list.remove(ans1*3);ans1*=3;continue;}break;}for (Long l : deque) {dduo(l+" ");}}public static void main(String[] args) throws Exception {int t = 1;
//        t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t) {System.out.print(t);}static <T> void dduoln() {System.out.println("");}static <T> void dduoln(T t) {System.out.println(t);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}