// @Title: 滑动窗口最大值 (Sliding Window Maximum)
// @Author: qisiii
// @Date: 2022-03-04 14:38:31
// @Runtime: 32 ms
// @Memory: 54.4 MB
// @comment: 使用双向队列
// @flag: BLUE
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length<1||k<=0){
            return new int[0];
        }
        Deque<Integer> deque=new LinkedList();
        int[] result=new int[nums.length-k+1];
        int index=0;
        //先获取第一个窗口的最大值队列
        for (int i = 0; i < k; i++) {
            //当新值大于队尾的时候，弹出队尾
            while(!deque.isEmpty()&&nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offer(i);
        }
        result[index]=nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            //当队首不在窗口内时，出队
            if(deque.peekFirst()<=i-k){
                deque.pollFirst();
            }
            //当新值大于队尾的时候，弹出队尾
            while (!deque.isEmpty()&&nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offer(i);
            result[++index]=nums[deque.peekFirst()];
        }
        return result;
    }
}

// @Title: 滑动窗口最大值 (Sliding Window Maximum)
// @Author: qisiii
// @Date: 2024-09-14 17:01:19
// @Runtime: 29 ms
// @Memory: 58.7 MB
// @comment: 单调递减队列用来存储可能为最大值的下标，然后在移动窗口的时候保证这个队列的性质
// @flag: GREEN
class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[i]>nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offer(i);
        }
        int[] result = new int[nums.length - k + 1];
        result[0]=nums[queue.peekFirst()];
        for(int i=k;i<nums.length;i++){
            if(queue.peekFirst()<i-k+1){
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[i]>nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offer(i);
            result[i-k+1]=nums[queue.peekFirst()];
        }
        return result;
    }
}