package LeetCode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class lc_239v2 {
    public static class myQueue {
        LinkedList<Integer> queue = new LinkedList<>();

        public void add(int val) {
            while (!queue.isEmpty() && val > queue.getLast()) queue.removeLast();
            queue.add(val);
        }

        public void pop(int val) {
            if (!queue.isEmpty() && val == queue.getFirst()) queue.removeFirst();
        }

        public int peek() {
            return queue.getFirst();
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length <= k) return nums;
        int[] res = new int[nums.length - k + 1];
        myQueue que = new myQueue();
        for (int i = 0; i < k; i++) {
            que.add(nums[i]);
        }
        int idx = 0;
        res[idx++] = que.peek();
        for (int i = k; i < nums.length; i++) {
            que.add(nums[i]);
            que.pop(nums[i - k]);
            res[idx++] = que.peek();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(nums,3)));
    }
}