题目内容

给定一个长度为 $n$ 的数组 $a$ (下标从 $1$ 开始),对于所有 $i∈[1,n]∩Z$ ，求出区间 $[1,i]$ 中第 $k$ 小的数。其中 $k$ 为给定常数。

题面描述

给定一个长度为$n$的数组$a$下标从$1$开始对于所有$i∈[1,n]∩Z$，求出区间 $[1, i]$ 中第$k$小的数。其中$k$为给定常数。如果区间内的数的数量不足$k$个，请输出$-1$。

思路

1. 使用最大堆 为了高效地求出每个前缀区间 $[1, i]$ 的第 $k$ 小的数，我们可以使用最大堆来动态维护前 $k$ 小的元素。

最大堆：最大堆的特性是堆顶元素是堆中最大的元素。我们通过维护一个大小为 $k$ 的最大堆，可以确保堆中保存的是当前区间的前 $k$ 小的元素，而堆顶即为该区间的第 $k$ 小元素。