17370845950

本文介绍一种基于单调双端队列（deque）的线性时间算法，用于高效求解满足特定约束条件的动态窗口最大值索引问题，将原始 o(n·k) 暴力解法优化至严格 Θ(n) 时间复杂度。

该问题本质是带约束的滑动窗口最大值索引查询：对每个位置 i（0-indexed），需在区间 [i − k[i] + 1, i]（闭区间）内找到 x[s] 的最大值，并返回其最左出现的索引 j（即满足 x[j] == max{x[s] | s ∈ [i−k[i]+1, i]} 且 j 最小）。关键约束 (∀i ∈ [1, n−1]) 1 ≤ k[i+1] ≤ k[i] + 1 表明窗口长度 k[i] 变化平缓——每次最多增长 1，不会突增，这为设计 Θ(n) 算法提供了决定性突破口。

暴力解法使用切片加 max()，每轮扫描最多 k[i] 个元素，最坏总时间达 O(n·k_max)，不可接受。而标准「固定长度滑动窗口最大值」可用单调 deque 在 O(n) 解决，但本题窗口长度 k[i] 动态变化，且左边界非单调右移（因 k[i] 可能变小，导致左边界跳跃左移），因此需更精细的维护策略。

✅ 正确解法：单调递减双端队列（存储索引） + 左边界按需收缩

核心思想：维护一个 deque q，其中存储候选索引，满足：

• q 中索引对应 x 值严格递减（即 x[q[0]] > x[q[1]] > ...）；
• 所有 q 中索引均落在当前有效窗口 [L_i, i] 内，其中 L_i = i − k[i] + 1；
• q[0] 即为当前窗口最大值的最左索引（因我们按值递减存，相等时后入者不淘汰前者，但为保“最左”，实际应淘汰严格更小值，相等值保留左侧索引——故入队时若 x[new] >= x[back] 则弹出队尾，确保队列严格递减，自然保留更早（更左）的大值索引）。

关键操作：

• 入队（i）：从队尾弹出所有满足 x[j]
• 出队（过期）：检查队首索引 q[0]
• 查询：q[0] 即为所求索引（因队首始终是窗口内最大且最左的索引）。

由于每个索引最多入队、出队各一次，总操作数为 O(n)，故整体时间复杂度为 Θ(n)。

以下是完整 Python 实现：

from collections import deque

def max_index_in_dynamic_windows(x, k):
    n = len(x)
    result = [0] * n
    q = deque()  # 存储索引，对应x值严格递减

    for i in range(n):
        # Step 1: 计算当前窗口左边界 L = i - k[i] + 1
        L = i - k[i] + 1

        # Step 2: 移除队首过期索引（小于 L）
        while q and q[0] < L:
            q.popleft()

        # Step 3: 维护单调递减性：弹出队尾所有 <= x[i] 的索引
        # 注意：用 <= 而非 <，确保相等时保留左侧索引（更早入队者更左）
        while q and x[q[-1]] <= x[i]:
            q.pop()
        q.append(i)

        # Step 4: 队首即为当前窗口最大值的最左索引
        result[i] = q[0]

    return result

# 测试用例
x = [1000, 4, 3, 2, 500, 10, 1]
k = [1, 2, 2, 3, 2, 3, 1]
print(" ".join(map(str, max_index_in_dynamic_windows(x, k))))
# 输出: 0 0 1 1 4 4 6 ✅

⚠️ 注意事项：

• 约束 1 ≤ k[i+1] ≤ k[i] + 1 保证了左边界 L_i 的变化是“温和”的——它可能向左跳（当 k[i] 减小时），但绝不会无界回溯；deque 的 popleft 总次数仍被摊还为 O(n)。
• 本解法返回的是索引而非值，且当多个位置取到相同最大值时，自动返回最左侧索引（由单调队列中“相等时弹出旧索引”逻辑保证）。
• 不要误用线段树或稀疏表：它们可处理任意区间查询（O(n log n) 预处理 + O(log n) 查询），但本题因 k[i] 的特殊约束，存在更优的纯线性解法；强行套用会退化为 O(n log n)。

总结：利用窗口长度变化的平滑性，结合单调 deque 维护候选最大值索引，可在单次遍历中完*部查询，真正实现理论最优的 Θ(n) 时间复杂度，是经典滑动窗口算法的精巧拓展。