常见队列问题

滑动窗口的最大值
给定一个数组和窗口长度k,求每个窗口内的最大值

解题思路
使用双端队列

1. 从队尾加入新元素,从对头取出头元素
2. 队列从左往右,保持递减
3. 新加入的元素如果比队列内的小则弹出
4. 当队头元素的索引小于,窗口左边界的索引时,需要把队头移除
5. 不断取出队头则为每个窗口内的最大值

public class _滑动窗口的最大值 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6, 7, 6, 8, 7, 9};
        int k = 3;
        //应该输出 5 5 7 7 6
        System.out.printf(Arrays.toString(getWindowMax(nums, k)));
    }

    public static int[] getWindowMax(int[] nums, int k) {

        //使用双端队列

        Deque<Integer> queue = new LinkedList<Integer>();
        int[] maxArr = new int[nums.length - k+1];
        for (int i = 0; i < nums.length; i++) {

            //保持队列单调递减
            //当新加入元素大于 队列内元素时  弹出队列内元素
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.removeLast();
            }
            queue.addLast(i);

            int left = i - k + 1;
            if (left < 0) {
                continue;
            }

            if (left > queue.peekFirst()) {
                queue.removeFirst();
            }
            //System.out.println("left>>"+left);
            //System.out.println(queue.peekFirst());
            maxArr[left] = nums[queue.peekFirst()];
        }
        return maxArr;
    }
}