JZ64-滑动窗口的最大值

class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (num == null || num.length == 0 || size == 0) {
            return list;
        }
        for (int i = 0; i < num.length - size + 1; i++) {
            list.add(findMax(num, i, size));
        }
        return list;
    }

    private int findMax(int[] num, int start, int size) {
        int max = num[start];
        for (int i = 1; i < size; i++) {
            if (num[start + i] > max) {
                max = num[start + i];
            }
        }
        return max;
    }
}

class Solution2 {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (nums == null || size < 1 || nums.length < size) {
            return ret;
        }

        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            // 在队列不为空的情况下，如果队列尾部的元素要比当前的元素小，或等于当前的元素
            // 那么为了维持从大到小的原则，我必须让尾部元素弹出
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            // 不走 while 的话，说明我们正常在队列尾部添加元素
            queue.addLast(i);
            // 如果滑动窗口已经略过了队列中头部的元素，则将头部元素弹出
            if (queue.peekFirst() == (i - size)) {
                queue.pollFirst();
            }
            // 看看窗口有没有形成，只有形成了大小为 size 的窗口，我才能收集窗口内的最大值
            if (i >= (size - 1)) {
                ret.add(nums[queue.peekFirst()]);
            }
        }
        return ret;
    }
}