给定一个数字序列 n 和一个数字 K, 1 <= K <= n，我们要找到长度为K的连续子序列 使得子序列中最小的元素尽可能大。
我已经能够在 O(n*log(k)) 时间内完成，方法是将当前 k 个元素保存在二叉树中，并在遍历数组时分别添加和删除下一个元素和第一个元素。我怎么能在 O(n) 中做到这一点？
最佳答案
维护一个双端队列，其中包含(按顺序)窗口中小于窗口中所有后续元素的元素。在任何时候，窗口最小值都在双端队列的前面。向前扩展窗口:从双端队列的后面弹出大于或等于新元素的元素。将新元素推到背面。向前收回窗口:如果双端队列前面的元素索引即将离开窗口，则将其删除。
每一步维护双端队列的摊销成本为 O(1)。 ( A real-time algorithm also is possible. )
关于algorithm - 具有最大最小元素的固定长度连续子序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25704990/