[博客翻译]纯函数滑动窗口聚合算法

在 Haskell 中的竞技编程：栈、队列和单调滑动窗口 发布于 2024 年 11 月 27 日，标签为 挑战、Kattis、栈、队列、滑动窗口 和 单态 假设我们有一个长度为 (n) 的项目列表，并且我们想要在列表内考虑宽度为 (w) 的“窗口”（即连续的子序列）。 通过暴力方法，我们可以在 (O(nw)) 时间内计算每个窗口的总和：只需生成所有窗口并分别求和。但当然，我们可以做得更好：跟踪当前窗口的总和；每当我们将窗口向右滑动一个元素时，我们可以加上右边进入窗口的新元素并减去左边滑出窗口的元素。使用...