我几天前采访了亚马逊。我无法回答让我满意的一个问题。面试后我一直试图获得答案，但到目前为止我还没有成功。这是问题：

您有一个大小为n的整数数组。给您参数kwhere 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。
这些值的最小值就是1答案1。

我想出的最好的答案是复杂度O（n log
k）。我要做的是用第一个k元素创建一个二分搜索树，获取树中的最大值并将其保存在变量中minOfMax，然后与数组中的其余元素一起循环一个元素，删除前一个元素中的第一个元素二进制搜索树中的段，将新段的最后一个元素插入树中，获取树中的最大元素，然后将其与minOfMax剩下minOfMax的最小值进行比较。

理想答案必须是复杂度O（n）。谢谢。