剑指offer - 滑动窗口最大值

题目链接：https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&&tqId=11217&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路分析：遍历数组，使用一个队列维护一个单调递减的队列，队头放最大值。具体看下面的表格。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = num.length;
        // 注意考虑边界
        if (n == 0 || size > n || size == 0) return list; // 题目要求窗口大于数组长度返回空
        Deque<Integer> deque = new LinkedList<>();
        // 维护一个递减队列
        for(int i = 0; i < n; ++ i) {
            if (deque.size() != 0 && deque.peek() < i - size + 1) { // 删除不符合题意的头
                deque.poll();
            }
            while(deque.size() != 0 && num[deque.peekLast()] <= num[i]) { // 当前元素大就删除队尾
                deque.pollLast();
            }
            deque.add(i);
            if (i >= size - 1) {
                list.add(num[deque.peek()]);
            }
        }
        return list;
    }
    public static void main(String[] args) {
        new Solution().solution();
    }
    public void solution() {
        /**
         8
         2 3 4 2 6 2 5 1
         3
         */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[n];
        for(int i = 0; i < n; ++ i) {
            num[i] = sc.nextInt();
        }
        int size = sc.nextInt();
        ArrayList<Integer> list = maxInWindows(num, size);
        for(int x : list) {
            System.out.print(x + " ");
        }
    }
}