首页/Algo Bridge/单调队列 (Monotonic Queue)/LC_239
⚡ 在闪卡工作台中刷此桥梁
🌉 单题同构迁移解析LC_239 · 困难

LC_239 (滑动窗口最大值) ➔ Paged Attention

单调队列维护窗口最大值的思想,与 Online Softmax 动态更新 running max 完全等价。

1️⃣ 经典算法母体 (LeetCode Origin)

LC_239 · 滑动窗口最大值

所属范式:单调队列 (Monotonic Queue) — 双端队列(Deque)同时维护时间有效性与数值单调性。新元素入队时尾部弹出劣解,头部定期淘汰过期滑出窗口的元素,实现滑动窗口最值在 O(1) 均摊时间查询。

⚡ 查看 LC-239 算法原题精解 ➔
2️⃣ 大模型工业系统落地 (Production AI System)

vLLM PagedAttention 分页虚拟显存与连续批调度 · Paged Attention

工程映射场景:单调结构追踪历史分块最大 Logit,实现无需落盘 GPU HBM 的核函数计算

🧬 对应工业算子接口签名
def paged_attention(Q: torch.Tensor, K_cache: torch.Tensor, V_cache: torch.Tensor, block_tables: torch.Tensor, context_lens: torch.Tensor, block_size: int = 16) -> torch.Tensor

🔗 同源拓展迁移桥梁

LC_239 ➔ 在线分块 Softmax (Online Softmax)
单调队列维护窗口最大值的思想,与 Online Softmax 动态更新 running max 完全等价。...
LC_239 ➔ Flash Attention (Tiled)
单调队列维护窗口最大值的思想,与 Online Softmax 动态更新 running max 完全等价。...
LC_239 ➔ Sliding Window Attention
单调队列维护窗口最大值的思想,与 Online Softmax 动态更新 running max 完全等价。...
LC_146 ➔ Paged Attention
大模型推理最容易 OOM,LRU 缓存机制直接决定了多请求高并发下谁的显存被换出到 CPU。...
LC_460 ➔ Paged Attention
高频 System Prompt 绝不应该被偶然的大请求挤出显存,LFU 提供频次保护。...
LC_380 ➔ Paged Attention
数组 + 哈希表的结合是实现真正 O(1) 均匀随机采样的唯一数学结构。...
← LC_239 (滑动窗口最大值) → FlashAttention 与 Online Softmax 片上分块加速LC_215 (数组中的第K个最大元素) → DeepSeek-R1 / o1 MCTS 蒙特卡洛树搜索与反思回溯 →