题解 | #【模板】滑动窗口#

哪来的双指针？

1. 我实在想不出来双指针的解法.
2. 还是用了单调递减队列来做的。 具体代码如下：

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] firstLine = in.nextLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int k = Integer.parseInt(firstLine[1]);
        int[] data = new int[n];
        String[] line = in.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(line[i]);
        }
        int[] maxArr = getMaxValueInWindow(k, data);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < maxArr.length - 1; i++) {
            sb.append(maxArr[i]).append(" ");
        }
        sb.append(maxArr[maxArr.length - 1]);
        System.out.println(sb);
    }

    public static int[] getMaxValueInWindow(int k, int[] data) {
        Deque<Integer> deque = new LinkedList<>();
        int i = 0;
        int j = 0;
        while (j < k) {
            int d = data[j];
          // 维持单调递减队列
            while (!deque.isEmpty() && data[deque.getLast()] < d) {
                deque.removeLast();
            }
            deque.addLast(j);
            j++;
        }
        int[] ret = new int[data.length - k + 1];
        while (j <= data.length) {
            // 取最大值
            ret[i] = data[deque.getFirst()];
            i++;
            if (deque.getFirst() < i) {
                deque.removeFirst();
            }
            if (j == data.length) {
                break;
            }
            int d = data[j];
          // 维持单调递减队列
            while (!deque.isEmpty() && data[deque.getLast()] < d) {
                deque.removeLast();
            }
            deque.addLast(j);
            j++;
        }
        return ret;
    }
}