是否存在亚O(N*W)的滑动窗口固定X点最大斜率计算算法？

问题定义 #

给定两个序列H[t]、F[t]和窗口大小W，需要生成序列M[t]，其中M[t]是点(t-1, H[t-1])到窗口内所有点(k, F[k])（k的范围是t到t+W）的直线斜率的最大值。

图形说明：当t=0时，M[0]对应图中蓝色直线的斜率（注：图中未展示完整的H[t]序列，仅显示了H[t=0]这个Y轴截距）。

该问题用于生成“松散”的信号包络。实际场景中，H[t-1]的值依赖于前一个窗口的M[t-1]，但这一细节不影响核心算法的设计。核心约束是：这是在线处理流程，无法提前获取窗口外的数据，必须实时输出每个窗口的计算结果。

现有解法的局限 #

• 暴力解法：时间复杂度为O(N*W)，即对每个窗口遍历所有F[t..t+W]内的样本计算斜率。但当窗口大小在2k到20k样本区间时，该方法无法满足实时性要求。
• 双端队列（Deque）尝试：最初打算借鉴滑动窗口最大值问题的双端队列解法，但发现H[t]的变化会破坏斜率的全序关系——如果H[t]相对于两个样本形成的直线切换到另一侧，这两个样本对应的斜率大小关系会反转，导致双端队列的维护逻辑失效。此外，该方法整体时间复杂度为O(N)（平均每个窗口O(1)操作），但在某些窗口需要清空整个队列时会出现O(W)的性能波动（不过其常数可能足够小，或许可以接受）。
• 二叉搜索树（BST）尝试：通过维护样本值的BST来实现窗口更新，每次更新的时间复杂度为O(log(W))，但尝试结合其他数据结构或数学性质减少斜率计算次数时遇到瓶颈——快速查询X和Y值并不意味着能快速找到最大的斜率（斜率本质是(Y2-Y1)/(X2-X1)，无法直接通过X/Y的单独查询得到）。

额外问题 #

这个问题有没有更简洁的通用名称？

内容的提问来源于stack exchange，提问作者NullCover