arrays - 如何找到所有大小为 k 的子数组的第 n 个最小值/最大值（滑动窗口问题）

Question

有很多参考可以找到所有大小为 k 的子数组的最小值/最大值，但是如何以最佳方式找到第 n 个最大值/最小值。如果我们必须找到子数组的最小/最大值，那么我们可以使用具有线性时间复杂度的双端队列解决方案。但是对于第 n 个最小值/最大值，我无法找到解决方案。

注意：n<=k

示例：arr = {7,1,4,20,11,17,15} n=2, k=4

输出：4,4,11,15

标签： arraysalgorithmdata-structures

Answer 1

我相信您需要的数据结构是经过一点修改的二叉搜索树 (BST)，其中每个节点还存储其子树的大小。

在 BST 中添加、删除元素或查找第 n 个元素都将变为log(K)*。因此，当在数组上滑动窗口时，您有 3 个log(K)操作，假设N给定数组中的总元素，因此总时间复杂度为N*log(K).

• 你需要一个平衡的 BST（例如红黑树）来维持这个时间复杂度。如果您来自任何在线评委，例如 Codeforce 或 Hackerrank，请记住他们往往会提供会产生退化 BST 的输入。