单调队列的操作

  1. 对头出队：head++ or deque.pollFirst();
  2. 队尾入队：++tail or deque.addLast()

（1）：直接入队：++tail
（2）：先删除再入队：tail—，++tail

滑动窗口最大值

【题目】给定一个长度为n的数组和一个大小为m的滑动窗口（0<m<=n），请找出所有滑动窗口里的最大值。例如，数组{2，6，4，9，8，5，5，2}，滑动窗口大小为3，那么，一共存在6个滑动窗口，它们的最大值分别为：{6，9，9，9，8，5}。

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3. //朴素实现方式
  4. class Main {
  5.     //8 3
  6.     //2,6,4,9,8,5,5,2
  7.     //[6, 9, 9, 9, 8, 5]
  8.     public static void main(String[] args) {
  9.         Scanner scanner = new Scanner(System.in);
  10.         int n = scanner.nextInt();
  11.         int m = scanner.nextInt();
  12.         scanner.nextLine();
  13.         String inputStr = scanner.nextLine();
  14.         String[] strArr = inputStr.split(",");
  15.         int[] nums = new int[n];
  16.         for (int i=0; i<n; i++) {
  17.             nums[i] = Integer.parseInt(strArr[i]);
  18.         }
  19.         System.out.println(Arrays.toString(windowMaxValue(nums, m)));
  20.     }
  21.     //实现该函数
  22.     public static int[] windowMaxValue(int[] nums, int m) {
  23.         int[] res = new int[nums.length-m+1];
  24.         for (int i=m-1; i< nums.length; i++) {
  25.             int temp = nums[i];
  26.             for (int j=i-m+1; j<i; j++) {
  27.                 temp = Math.max(nums[j], temp);
  28.             }
  29.             res[i-m+1] = temp;
  30.         }
  31.         return res;
  32.     }
  33. }
import java.util.Arrays;
import java.util.Scanner;
public class MultiPackagePro {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        String input = scanner.nextLine();
        String[] inputs = input.split(",");
        int[] nums = new int[n];
        for (int i = 0; i < inputs.length; i++) {
            nums[i] = Integer.parseInt(inputs[i]);
        }
        System.out.println(Arrays.toString(windowMaxValuePro(nums, n, m)));
    }
    //单调队列
    public static int[] windowMaxValuePro(int[] nums, int n, int m) {
        int[] res = new int[n-m+1];
        int[] queue = new int[n]; //模拟队列，存储的是下标
        int head = 0, tail = -1;
        for (int i = 0; i < n; i++) {
            //不在窗口内，队头出队
            if (head<=tail && queue[head] < i-m+1) {
                head++;
            }
            //判断后出队
            while (head<=tail && nums[i]>=nums[queue[tail]]) {
                tail--;
            }
            queue[++tail] = i;
           if (i>=m-1) {
               res[i-m+1] = nums[queue[head]];
           }
        }
        return res;
    }
}

LeetCode 239 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //单调队列：出队和入队
        int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i=0; i<n; i++) {
            //队头存储的下标不在窗口种
            if (!deque.isEmpty() && i-k+1 > deque.getFirst()) {
                deque.pollFirst();
            }
            //队尾元素比插入的元素小，所以队尾出来，没有价值
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {
                deque.pollLast();
            }
            //入队
            deque.addLast(i);
            if (i>=k-1) { //要弹出来了
                res[i-k+1] = nums[deque.getFirst()];
            }
        }
        return res;
    }
}

连续子序列的最大和

【题目】给定一个长度为n的整数序列，请找出长度不超过m的连续子序列的最大和。例如数组{2，-3，5，2，-4，-1，8}，m取3，那么长度不超过3的连续子序列的最大和为8.
【分析】设计长度为3的窗口，来模拟查找。
【技巧】前缀和。先把数组转化为前缀和s[]，然后使用s[i]-min(s[j], j∈[i-m, i-1])求最大和，用滑动窗口找[i-m,i-1]的最小值即可。

//朴素的方式
import java.util.Scanner;
public class LongestSequentialSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        String string = scanner.nextLine();
        String[] strArr = string.split(",");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(strArr[i]);
        }
        //前缀和
        int[] sum = new int[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i-1] + nums[i];
        }
        System.out.println(maxSum(sum, n, m));
    }
    public static int maxSum(int[] nums, int n, int m) {
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            int minValue = Integer.MAX_VALUE;
            for (int j=i-m; j<i; j++) {
                if (j > 0) {
                    minValue = Math.min(minValue, nums[j]);
                }
            }
            res = Math.max(res, nums[i] - minValue);
        }
        return res;
    }
}

//单调队列寻找窗口最小值
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class LongestSequentialSumPro {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        String string = scanner.nextLine();
        String[] strArr = string.split(",");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(strArr[i]);
        }
        //前缀和
        int[] sum = new int[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i-1] + nums[i];
        }
        System.out.println(maxSumPro(sum, n, m));
    }
    public static int maxSumPro(int[] nums, int n, int m) {
        int res = nums[0];
        //使用单调队列寻找最小值，此处窗口不包含当前值
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(0);
        for (int i = 0; i < n; i++) {
            //出队和入队
            if (!deque.isEmpty() && deque.getFirst() < i-m) deque.pollFirst();
            res = Math.max(res, nums[i]-nums[deque.getFirst()]);
            while (!deque.isEmpty() && nums[deque.getLast()] > nums[i]) deque.pollLast();
            deque.addLast(i);
        }
        return res;
    }
}