寻求可变范围最大强度查询的线性时间复杂度(Theta(n))算法

问题概述 #

给定两个长度相等的列表x和k：

• x：存储队列中每个生物的强度值
• k[i]：第i个生物可调用的前方生物数量（包含自身），即该生物的取值范围为**从max(0, i - k[i] + 1)到i**的连续子数组（共k[i]个元素，若i - k[i] + 1 < 0则从列表开头开始）

需要生成一个结果列表，每个元素对应每个生物能获取的最大强度值。

示例 #

输入：
x = [5, 10, 7, 2, 20]，k = [1, 2, 1, 3, 2]

• 索引3的生物：k[3]=3，取值范围为索引1到3（[10,7,2]），最大值为10
• 最终结果：[5,10,7,10,20]

当前算法的局限性 #

现有实现为O(n²)时间复杂度，因为每个循环内调用max()遍历子数组，存在嵌套迭代：

def calculate_xj(x, k):
    x_j = []
    for i in range(len(x)):
        start_index = max(0, i - k[i])
        end_index = i + 1
        x_j.append(max(x[start_index:end_index]))
    return x_j

线性时间解决方案：单调队列 #

使用单调递减队列可以实现Θ(n)的时间复杂度，核心思路是维护一个队列，队列中存储的是元素的索引，且对应的x值严格单调递减，同时确保队列头部的索引始终在当前查询的窗口范围内。

算法步骤 #

1. 初始化一个双端队列deque，用于存储索引
2. 遍历每个元素的索引i：
   • 移除队列中所有小于当前窗口左边界的索引（左边界为max(0, i - k[i] + 1)）
   • 移除队列中所有对应x值小于等于x[i]的索引（保证队列单调递减）
   • 将当前索引i加入队列
   • 队列的头部即为当前窗口的最大值对应的索引，将x[队列[0]]加入结果列表

Python实现 #

from collections import deque

def calculate_xj_linear(x, k):
    n = len(x)
    result = []
    dq = deque()  # 存储索引，对应x值单调递减
    
    for i in range(n):
        # 当前窗口的左边界：最多取k[i]个元素，包含自身，所以左边界是i - k[i] + 1
        left = max(0, i - k[i] + 1)
        
        # 移除队列中不在窗口内的元素（索引小于左边界）
        while dq and dq[0] < left:
            dq.popleft()
        
        # 移除队列中所有x值小于等于当前x[i]的元素，保证队列单调递减
        while dq and x[dq[-1]] <= x[i]:
            dq.pop()
        
        dq.append(i)
        # 队列头部就是当前窗口的最大值索引
        result.append(x[dq[0]])
    
    return result

# 验证示例
x = [5, 10, 7, 2, 20]
k = [1, 2, 1, 3, 2]
print(calculate_xj_linear(x, k))  # 输出: [5, 10, 7, 10, 20]

复杂度分析 #

• 时间复杂度：Θ(n)，每个元素最多被加入和移除队列各一次，总操作次数为O(n)
• 空间复杂度：O(n)，最坏情况下队列存储所有元素（如x严格递减时）

关键说明 #

• 单调队列的核心是避免重复计算：每个元素只被处理一次，后续查询直接复用之前的最大值信息
• 动态调整窗口左边界，确保队列中的索引始终在当前有效范围内

内容的提问来源于stack exchange，提问作者Lukáš Kocián