package Code;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Code239 {
    static int[] maxWindow(int[] nums, int k){
        if(nums == null || nums.length == 0 || k<=0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n-k +1];
        Deque<Integer> q = new LinkedList<>();
        for(int i = 0; i< n; i++){
            if(!q.isEmpty() && q.peekFirst()< i-k+1){
                q.pollFirst();// 移除队列中不在当前窗口内的元素
            }
            while(!q.isEmpty() && nums[q.peekLast()]< nums[i]){ // 移除队列中比当前元素小的元素
                q.pollLast();
            }
            q.offer(i);
            if(i >=k-1){
                res[i-k+1] = nums[q.peekFirst()];
            }

        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(IntStream.of(maxWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)).boxed().toList());
        System.out.println(Arrays.stream(maxWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)).boxed().toList());
    }
}