本文介绍一种基于单调双端队列（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) 时间复杂度，是经典滑动窗口算法的精巧拓展。
