leetcode第2022题：滑动窗口的最大值
题目描述：
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
例如：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

package datastruct;

import java.util.*;

/**
 * @Author: jxy
 * @Date: 2021/4/3 11:37
 */
public class SlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 1) {
            return nums;
        }
        //定义单调双端队列  (递减)
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        int index = 0;
        while (index < nums.length) {
            int indexNum = nums[index];
            if (deque.isEmpty()) {
                deque.offer(indexNum);
            } else {
                //构建最大值队列
                while (deque.size() > 0 && deque.peekLast() < indexNum) {
                    deque.pollLast();
                }
                deque.offer(indexNum);
            }
            //移动窗口时，如果当前窗口不包含原窗口中的最大值，需要将之前的最大值从单调队列中移除掉
            if (index > k-1) {
                if (deque.peekFirst() == nums[index-k]) {
                    deque.pollFirst();
                }
            }
            //形成窗口
            if (index >= k-1) {
                //将当前窗口的最大值添加到结果集中
                result[index+1-k] =deque.peekFirst();
            }
            index++;
        }
        return result;

    }

}

leetcode第1900题：队列中的最大值

package datastruct;

import java.util.ArrayDeque;

/**
 * 需要维护一个普通队列 和一个单调的队列
 *
 * @Author: jxy
 * @Date: 2021/4/3 8:57
 */
public class MaxQueue {

    private  ArrayDeque<Integer> queue = new ArrayDeque<>();
    private  ArrayDeque<Integer> maxValQueue = new ArrayDeque<>();

    public MaxQueue() {

    }

    public int max_value() {
        if (maxValQueue.size() == 0) {
            return -1;
        }
        return maxValQueue.peek();

    }

    public void push_back(int value) {
        queue.offer(value);
        if (maxValQueue.size() == 0) {
            maxValQueue.offer(value);
        } else {
            Integer last = maxValQueue.peekLast();
            while (last != null && last < value) {
                maxValQueue.pollLast();
                last = maxValQueue.peekLast();
            }
            maxValQueue.offer(value);
        }
    }

    public int pop_front() {
        Integer result = -1;
        if (queue.size() == 0) {
            return result;
        }
        result = queue.pollFirst();
        if (result.compareTo(maxValQueue.peekFirst()) == 0) {
            maxValQueue.pollFirst();
        }
        return result;

    }

}