package com.zmz.algorithm.stackQueue;

import java.util.*;

/**
 * @author 张明泽
 * Create by 2022/6/1 8:44
 * 滑动窗口最大值
 * LeetCode-239
 */

/**
 * 虽说某几个方法等价，但是我们在使用的时候，建议根据用途来使用不同的方法，
 * 比如你想把LinkedList当做集合list，那么应该用add/remove，
 * 如果想用作队列，则使用offer/poll，
 * 如果用作栈，则使用push/pop，
 * 如果用作双端队列，则使用offerFirst/offerLast/pollFirst/pollLast。
 * 根据语义使用，就不会发生：我想删队尾，结果删了队头这种事了。
 */
public class MaxSlidingWindow {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int[] result = max(nums,3);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 双端队列
     * 队列中存的是数组下标
     * 因为这样既可以 判断位置 还能得出 最大值
     */
    public static int[] max(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            // 判断 头结点 是否在 [i - k + 1, i] 范围内,否则弹出 省的元素一定在滑动窗口内了
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            // 使其单调,从小到大,确保每次放进去的比末尾都大,否则弹出 不管剩不剩元素 首节点一定是滑动窗口内最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            // 确定好窗口位置 队列首元素最大
            if (i >= k - 1) {
                res[index++] = nums[deque.peek()];
            }
        }
        return res;
    }
}