package com.cyy.test_t_6_;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Description 剑指Offer t_64- 滑动窗口的最大值
 * 题目描述
 * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
 * 例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
 * 他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
 * {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}，
 * {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
 *
 *  思路分析：
 *  基于最大堆实现。
 *  遍历数组，当没有达到滑动窗口最大值，数据直接加入最大堆，当到达滑动窗口最大值，此时的堆顶即是当前滑动窗口
 *  最大值，将其保存到结果集，此时将数组中第一个加入堆的
 *  数据移出最大堆，将数组新元素加入最大堆，等滑动窗口到达数组的最右边，此时将最后一个滑动窗口的最大值即
 *  此时最大堆的堆顶加入结果集
 * @Author Crystal
 * @Date 2019/8/04 07:09
 * @Version 1.0
 **/
public class t_64 {

    public static ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();

        if(num.length <= 0 || size <= 0 || num.length < size) return result;

        //最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(size, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for(int i = 0; i < num.length; i ++){
            if(maxHeap.size() < size){
                maxHeap.offer(num[i]);
            } else {
                //此时的对顶元素就是当前滑动窗口最大值
                result.add(maxHeap.peek());
                //先移除数组第一个元素
                maxHeap.remove(num[i - size]);
                //再加入一个新的元素
                maxHeap.offer(num[i]);
            }
        }
        //当到达最后一个滑动窗口，需要将对顶结果加入结果集，不然最后一次不会进入上面的循环
        result.add(maxHeap.peek());
        return result;
    }

    public static void main(String[] args) {
        int [] n = {2,3,4,2,6,2,5,1};
        maxInWindows(n,3).forEach(e -> System.out.println(e));

    }
}