双栈滑动窗口聚合：为无逆运算的聚合而生
来源：orlp.net — 2026-10-02
📋 概述
orlp 介绍了“双栈滑动窗口聚合”算法：用两个栈把任意可结合的聚合运算（最小值、分位数、HyperLogLog 近似去重等）维护在滑动窗口上，达到摊还 O(1) 的每步复杂度。与使用双端队列的经典做法不同，它不要求运算存在逆元，因此也避开了浮点求和一旦遇到 NaN 就永远为 NaN 的问题。该算法被论文追溯到 2011 年的 Stack Overflow 帖与 2001 年的讲义。
🔑 核心要点
- 用 两个栈 维护滑动窗口聚合，摊还 O(1) 每步
- 适用于 无逆元的聚合：最小值、分位数、HyperLogLog 去重等
- 抽象为 empty/unit/combine/finalize 四个函数以覆盖多种聚合
- 避免浮点求和遇 NaN 后永久污染 结果的经典陷阱
- 算法可追溯至 2011 年 Stack Overflow 帖与 2001 年 Sleator 讲义
💡 金句
我从一篇更进阶的论文中读到这个算法……他们描述了一个“双栈”算法，摊还 O(1)，而且远比其他做法简单。
👍 0
👎 0
← 返回 Lobsters 首页