Sliding Window Median

题目描述

给你一个由 n 个整数组成的数组。你的任务是从左到右计算每个大小为 k 的滑动窗口的中位数。 中位数是在元素排序后处于中间的元素。如果元素个数为偶数，则有两个可能的中位数，我们假定中位数为较小的那一个。

输入格式

第一行包含两个整数 n 和 k：元素个数和窗口大小。 然后有 n 个整数 x_1,$\ldots$,x_n：数组的内容。

输出格式

输出 n-k+1 个值：中位数。

8 3
2 4 3 5 8 1 2 1

3 4 5 5 2 1

提示

$1 \le k \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$

标签: CSES1076|滑动窗口

来源

CSES1076|滑动窗口