质量检测

GitHub跳转原题关系图返回列表

单调递增 deque 保存窗口内仍可能成为最小值的下标。

OJ: luogu

题目 ID: P2251

难度:普及/提高-

标签:单调队列滑动窗口dequepython

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

输出每个固定宽度窗口的最小值。

思路

队列保存下标且对应值严格递增。加入新值时，队尾不小于它的元素以后不可能成为最小值，全部弹出；队首若离开窗口也弹出。形成完整窗口后，队首值就是答案。

Python 知识

  • collections.deque 支持两端 O(1)O(1) 删除。
  • 队列存下标而非值，才能判断元素是否过期。
  • enumerate(values) 同步取得窗口右端和新值。

代码

python
import sys
from collections import deque


data = iter(map(int, sys.stdin.buffer.read().split()))
n, width = next(data), next(data)
values = [next(data) for _ in range(n)]
queue = deque()
answers = []

for i, value in enumerate(values):
    while queue and values[queue[-1]] >= value:
        queue.pop()
    queue.append(i)
    if queue[0] <= i - width:
        queue.popleft()
    if i + 1 >= width:
        answers.append(str(values[queue[0]]))
print("\n".join(answers))

复杂度

每个下标进出队各一次，时间 O(n)O(n)，空间 O(m)O(m)。

总结

固定窗口最值的标准结构是单调队列，不需要堆的懒删除和对数因子。