5

给定一个大小为 n 的数组，即它有 n 个元素。和窗口大小'W'。您必须在所有大小为“W”的子数组中找到最大值。从索引 0 开始。

Sample Input:
n=10 , W = 3 // n is number of element in array and W is window size.

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

我尝试了什么 - （自平衡 BST）

  1. 选择前 k 个元素并创建一个大小为 W 的自平衡二叉搜索树 (BST)。
  2. 为 i = 0 到 n – W 运行一个循环
    1. 从 BST 中获取最大元素，并打印它。
    2. 在 BST 中搜索 arr[i] 并将其从 BST 中删除。
    3. 将 arr[i+W] 插入 BST。

时间复杂度：

  1. 第 1 步是O(WLogW).
  2. 步骤 2.1、2.2 和 2.3 的时间复杂度为O(LogW). 由于 2.1、2.2 和 2.3 的步骤是在一个循环中运行n-W+1 times的，因此完整算法的时间复杂度O(WLogW + (n-W+1)*LogW) 也可以写为O(nLogW)。

我的问题是我可以改进它吗？关于 BST 方法的任何建议或我没有听说过的任何其他算法？

我到处都只看到出队方法。没有任何方法吗？

4

0 回答 0