一道例题,给定一串数字,求每连续k个数字的最大、最小值。
思路:初始化一个初始长度为k的单调队列,按从左到右加入元素,同时满足这个队列中的元素是递减的(也就是假如某个数被两个距离不超过k的大于他的数夹着,他会被从队尾调出队列)。得到最大值。
向右移动一格,假如队首离开范围,出队。往队尾加入元素前,把队尾的所有比它小的元素全部出队。
得到新的最大值。
模板 - 数据结构 - 单调队列
原文:https://www.cnblogs.com/Yinku/p/10472977.html