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 {
        // todo
        n=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());
    }
}