滑动窗口

思路:单调队列

以求最小值为例

  • 在读取每一个数 ai 的过程中,判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了,因为它已经不可能成为现在及以后所有窗口内的最小值,不妨弹出,重复以上操作,直到ai小于队尾的数,再把ai放到队尾
  • 当现在的长度已经达到窗口的长度时,每一次都会输出最小值,因为队列是单调递减的,第一个数一定是现在窗口内最小的数,直接输出
  • 在队尾添加的过程中,要始终保证队列里的数都在窗口内,当区间长度大于窗口长度时,要从队首弹出
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×