解法一:

考虑到先在第一个窗口内找到最大值,每次右移窗口时,将新增的那个数与原窗口最大值进行比较,若比上一个窗口的最大值还大,那么毋庸置疑新进的数为本窗口的最大值。否则重新在新窗口内进行比较寻找最大值。(注:此方法在牛客只有14/21用例通过,会报超时)

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        int max = Integer.MIN_VALUE; // 表示java里整型的最小值
        for (int i = 0; i < size; i++) { // 找到第一个窗口的最大值
            if (num[i] > max) {
                max = num[i];
            }
        }
        list.add(max); // 将第一个窗口的最大值添加进要返回的list中
        for (int i = size; i < num.length; i++) {
            if (num[i] >= max) { // 如果新进的值大于max,则更新max的值,即新值为本轮窗口最大值
                max = num[i];
            } else { // 否则将新进值设为max,从后往前开始寻找最大值
                max = num[i];
                for (int k = i - 1; k > i - size; k--) { 
                    if (num[k] > max) {
                        max = num[k];
                    }
                }
            }
            list.add(max);
        }
        return list;
    }
}

解法二:双端队列

1. deque 内仅包含窗口内的元素,且存储的是窗口内的递减序列
2. deque 内的元素非严格递减,每轮添加了新的元素后,需要deque内小于该元素的元素全部删除。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (size == 0 || size > num.length) return list;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            //弹出队列中小于当前元素的所有元素,保证单调性
            while (!deque.isEmpty() && num[i] > num[deque.peekLast()]) {
                deque.pollLast();
            }
            //当前元素入队
            deque.offerLast(i);
            //若队首元素已不在滑动窗口内,则弹出
            if (i - deque.peekFirst() + 1 > size) {
                deque.pollFirst();
            }
            //取出最大值
            if (i >= size - 1) {
                list.add(num[deque.peekFirst()]);
            }
            
        }
        return list;
    }
}