import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.TreeSet;

public class _480 {
    //解法 1. 双优先队列 2.TreeMap 3.TreeSet +下标
    static class Solution1 {
        public double[] medianSlidingWindow(int[] nums, int k) {
            //双优先队列
            //大顶堆，加小顶堆
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
            //这里要小心，必须得用比较，如果使用b-a可能会导致溢出出错
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> {
                if (b == a) return 0;
                return b > a ? 1 : -1;
            });
            //放入堆
            int limit = k / 2 == 0 ? 1 : k / 2;
            double[] res = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i >= k) {
                    Integer remove = nums[i - k];
                    //从大顶堆删除后，要将小顶堆堆顶元素放入大顶堆
                    if (remove <= maxHeap.peek()) {
                        maxHeap.remove(remove);
                        if (minHeap.size() > 0) {
                            maxHeap.offer(minHeap.poll());
                        }
                    } else {
                        minHeap.remove(remove);
                    }
                }
                //1. 大顶堆没满，放大顶堆
                //2. 大顶堆满，如果nums[i] > maxHeap.peek(),直接放小顶堆，
                //否则，大顶堆出放小顶堆，然后放大顶堆
                if (maxHeap.size() == limit) {
                    if (nums[i] >= maxHeap.peek()) {
                        minHeap.offer(nums[i]);
                    } else {
                        minHeap.offer(maxHeap.poll());
                        maxHeap.offer(nums[i]);
                    }
                } else {
                    maxHeap.offer(nums[i]);
                }
                if (i >= k - 1) {
                    res[i - k + 1] = k % 2 == 0 ? ((long) maxHeap.peek() + (long) minHeap.peek()) / 2.0 : minHeap.peek() != null ? minHeap.peek() : maxHeap.peek();
                }
            }
            return res;
        }
    }

    static class Solution2 {
        public double[] medianSlidingWindow(int[] nums, int k) {
            //优先队列删除元素时间复杂度为O(N)
            //使用TreeMap,删除元素的时间复杂度为O(lgN);
            //总时间复杂度 lgk * N;
            TreeMap<Integer, Integer> min = new TreeMap<>();
            TreeMap<Integer, Integer> max = new TreeMap<>();
            int minSize = 0;
            int maxSize = 0;
            int limit = k / 2;
            double[] res = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i >= k) {
                    if (maxSize > 0 && nums[i - k] <= max.lastKey()) {
                        reduce(max, nums[i - k]);
                        maxSize--;
                        if (minSize > 0) {
                            Integer key = min.firstKey();
                            reduce(min, key);
                            add(max, key);
                            minSize--;
                            maxSize++;
                        }
                    } else {
                        reduce(min, nums[i - k]);
                        minSize--;
                    }
                }
                if (maxSize == limit) {
                    add(max, nums[i]);
                    Integer key = max.lastKey();
                    reduce(max, key);
                    add(min, key);
                    minSize++;
                } else {
                    add(max, nums[i]);
                    maxSize++;
                }
                if (i >= k - 1) {
                    res[i - k + 1] = k % 2 == 0 ? ((double) max.lastKey() + (double) min.firstKey()) / 2.0 : min.firstKey();
                }
            }
            return res;
        }

        public void add(TreeMap<Integer, Integer> m, Integer key) {
            Integer c = m.getOrDefault(key, 0);
            m.put(key, c + 1);
        }

        public void reduce(TreeMap<Integer, Integer> m, Integer key) {
            Integer c = m.getOrDefault(key, 0);
            if (c == 0) throw new RuntimeException("删除错误");
            if (c == 1) {
                m.remove(key);
                return;
            }
            m.put(key, c - 1);
        }
    }

    static class Solution3 {
        //时间复杂度 lgK * N;
        public double[] medianSlidingWindow(int[] nums, int k) {
            //TreeSet存下标
            Comparator<Integer> comparator = (a, b) -> {
                if (nums[a] == nums[b]) return a - b;//这里要小心，必须消除重复，否则会被覆盖
                return nums[a] > nums[b] ? 1 : -1;
            };
            TreeSet<Integer> min = new TreeSet<>(comparator);
            TreeSet<Integer> max = new TreeSet<>(comparator);
            int limit = k / 2;
            double[] res = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i >= k) {
                    if (max.size() > 0 && nums[i - k] <= nums[max.last()]) {
                        max.remove(i - k);
                        if (min.size() > 0) {
                            max.add(min.pollFirst());
                        }
                    } else {
                        min.remove(i - k);
                    }
                }
                if (max.size() == limit) {
                    max.add(i);
                    min.add(max.pollLast());
                } else {
                    max.add(i);
                }
                if (i >= k - 1) {
                    res[i - k + 1] = k % 2 == 0 ? ((double) nums[max.last()] + (double) nums[min.first()]) / 2.0 : nums[min.first()];
                }
            }
            return res;
        }
    }
}