相关疑难解决方法(0)

我几天前采访了亚马逊.我无法回答其中一个让我满意的问题.我在采访后试图得到答案,但到目前为止我还没有成功.这是一个问题:

你有一个大小为n的整数数组.给你参数k在哪里k < n.对于k阵列中每个连续元素大小的每个段,您需要计算最大值.您只需返回这些最大值的最小值.

例如给出1 2 3 1 1 2 1 1 1,k = 3答案是1.
该段将是1 2 3,2 3 1,3 1 1,1 1 2,1 2 1,2 1 1,1 1 1.
每个段中的最大的值是3,3,3,2,2,2,1.因此,答案是
这些值中的最小值.11

我想出的最佳答案是复杂度O(n log k).我所做的是创建一个带有第一个k元素的二叉搜索树,获取树中的最大值并将其保存在变量中minOfMax …

问题是在长度为n的数组中找到大小为k的每个子阵列中的最大值.

蛮力方法是O(nk).但是使用双端队列,解决方案应该是O(n).但是我不相信它会到达O(n),特别是因为这个while循环:

# Remove all elements smaller than 
# the currently being added element  
# (Remove useless elements) 
while Qi and arr[i] >= arr[Qi[-1]] : 
    Qi.pop()

它位于从k到n的for循环内部.难道这技术上不会每个循环运行k次,介于O(n)和O(kn)之间？即使对于deque解决方案,最坏情况下的时间复杂度实际上是O(kn)吗？

给定一个大小为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方法的任何建议或我没有听说过的任何其他算法？

我到处都只看到了Dequeue Method.是不是有任何方法？

给定一个由N个元素组成A[0 .. N - 1]的数组，则产生一个数组B，使得：

 B[i] = min (A[i], A[i+1], ..., A[i+K-1]). 

（数组B将具有完全（N-k + 1）个元素。

时间复杂度应优于O（N * k）

我当时在考虑使用minheap ...但是，heapify会增加复杂性，而且蛮力是O（n * k）

同样，空间复杂度s小于O（k）

这是一个例子

Input: 
A={ 2,1,3,2,5,7,1}, N=7,k=3

Output:
B={1,1,2,2,1}