给定两个等长整数数组 `x`（元素为“能量值”）和 `k`（每个位置 `i` 定义窗口长度 `k[i]`），要求对每个 `i` 快速找出子数组 `x[i−k[i]+1 .. i]` 中最大值的**最左索引**，整体时间复杂度需严格为 Θ(n)。
该问题本质是带变长右对齐滑动窗口的最大值索引查询：窗口始终以当前下标 i 为右端点，左端点为 i − k[i] + 1（含），且 k 数组满足约束 k[i+1] ≤ k[i] + 1（即窗口长度变化平缓，不会突增）。这使得我们无法直接套用固定长度滑动窗口的经典单调队列解法，但该约束恰恰是突破口——它保证了窗口左边界随 i 增加而非递减（即左端点单调不降），因此可设计一个单次遍历 + 单调双端队列（deque） 的 Θ(n) 解法。
核心思想是：维护一个严格递减的双端队列 dq，存储的是数组 x 的下标，确保队首始终是当前有效窗口内的最大值索引。关键在于——由于 k[i] 变化受限，窗口左边界 left_i = i − k[i] + 1 是单调不减序列，因此我们可以在主循环中只做最多一次左边界收缩，避免重复扫描。
以下是完整、正确、Θ(n) 时间复杂度的 python 实现：
from collections import deque def max_index_for_each_k(x, k): n = len(x) result = [0] * n dq = deque() # 存储下标，对应 x 值严格递减 for i in range(n): # Step 1: 移除超出当前窗口左边界的所有下标 left_bound = i - k[i] + 1 while dq and dq[0] < left_bound: dq.popleft() # Step 2: 维护单调递减性：从队尾弹出所有 x[j] <= x[i] 的下标 j # 注意：此处用 <= 而非 <，是为了在值相等时保留更早（更左）的索引， # 从而自然满足“返回最左最大索引”的要求 while dq and x[dq[-1]] <= x[i]: dq.pop() # Step 3: 加入当前下标 dq.append(i) # Step 4: 队首即为当前窗口 [left_bound, i] 中最大值的最左索引 result[i] = dq[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_for_each_k(x, k)))) # 输出：0 0 1 1 4 4 6✅ 为什么这是 Θ(n)？
- 每个下标 i 最多入队 1 次、出队 1 次（popleft() 和 pop() 总次数 ≤ 2n）；
- left_bound 单调不减，因此 popleft() 在整个循环中总执行次数 ≤ n；
- 无嵌套循环，主循环 for i in range(n) 为 O(n)，内部操作均摊 O(1)。
⚠️ 关键注意事项：
- k[i] 必须满足题目约束 k[i+1] ≤ k[i] + 1（且 k[0] ≥ 1），否则左边界可能回跳，破坏单调性，导致算法失效；
- 使用 保留最早出现的下标（即最左索引），这与题意“返回最强大索引（即最大值的首次出现位置）”完全一致；
- 不要使用 x.index(max(...)) 或类似线性查找，那会退化为 O(n·k)；
- 段树或稀疏表虽可解一般 RMQ，但时间复杂度为 O(n log n) 预处理 + O(log n) 查询，总复杂度 O(n log n)，不满足本题 Θ(n) 要求。
综上，利用 k 数组的特殊单调性约束，结合单调双端队列维护“右对齐变长窗口”的最大值索引，是实现真正线性时间解法的唯一高效路径。