本文详解如何利用单调双端队列（deque）在线性时间内求解每个位置 i 对应长度为 k[i] 的左对齐滑动窗口中的最大值索引，满足约束条件 k[i+1] ≤ k[i] + 1，彻底避免 o(n·k) 的朴素遍历。
该问题本质是带变长窗口的滑动最大值索引查询：对每个下标 i（0-indexed），需在子数组 x[i − k[i] + 1 : i + 1]（即长度为 k[i]、右端点固定为 i 的窗口）中找出最大元素的最左出现索引（题目输出为 x.index(group)，但注意：当存在重复最大值时，list.index() 返回首次出现位置——而题例中 x[0]=1000 是全局最大且唯一，故实际要求的是「最大值在窗口内最靠左的索引」；结合样例输出 0 0 1 1 4 4 6 可确认：我们需返回窗口内最大值首次出现的全局索引，而非相对偏移）。
关键突破口在于题目给出的约束：
(∀i ∈ {1, ..., n−1})(1 ≤ k[i+1] ≤ k[i] + 1)
即 k 数组具有近似非递减+缓变特性：窗口长度每次最多增加 1，且不会突降。这一性质使我们能用单调双端队列（Monotonic Deque）维护候选最大值索引，并保证每个索引至多入队、出队各一次，实现 Θ(n) 总时间复杂度。
✅ 正确解法：单调 deque + 窗口动态收缩/扩展
我们维护一个双端队列 dq，其中存储可能成为未来窗口最大值的索引，按 x[index] 降序排列（队首最大）。同时，由于窗口右端点 i 逐个推进，而左端点 left_i = i − k[i] + 1 随 k[i] 动态变化，我们需要：
- 移除过期索引：若 dq[0]
- 维护单调性：在插入 i 前，从队尾弹出所有 x[j] ≤ x[i] 的索引 j（因 i 更新、值更大、存活时间更长）；
- 记录答案：dq[0] 即为当前窗口 [left_i, i] 中最大值的最左索引（因队列严格按值降序，且我们只删更小/更老的元素）。
⚠️ 注意：题干示例中 k 下标为 1-based 描述，代码中 k 为 0-based 数组。例如 i=1（第二元素）对应 k[1]=2，窗口为 x[1-2+1 : 1+1] = x[0:2] → [x0,x1]。
? Python 实现（Θ(n) 时间，O(n) 空间）
from collections import deque def sliding_max_indices(x, k): n = len(x) dq = deque() # 存储索引，对应 x 值单调递减 result = [] for i in range(n): # Step 1: 计算当前窗口左边界（含） left = i - k[i] + 1 # Step 2: 移除队首过期索引（小于 left） while dq and dq[0] < left: dq.popleft() # Step 3: 维护单调性 —— 从队尾移除所有 x[j] <= x[i] while dq and x[dq[-1]] <= x[i]: dq.pop() # Step 4: 加入当前索引 i dq.append(i) # Step 5: 队首即为窗口 [left, i] 中最大值的最左索引 result.append(dq[0]) return result # 测试样例 x = [1000, 4, 3, 2, 500, 10, 1] k = [1, 2, 2, 3, 2, 3, 1] print(sliding_max_indices(x, k)) # 输出: [0, 0, 1, 1, 4, 4, 6]
):
n = len(x)
dq = deque() # 存储索引，对应 x 值单调递减
result = []
for i in range(n):
# Step 1: 计算当前窗口左边界（含）
left = i - k[i] + 1
# Step 2: 移除队首过期索引（小于 left）
while dq and dq[0] < left:
dq.popleft()
# Step 3: 维护单调性 —— 从队尾移除所有 x[j] <= x[i]
while dq and x[dq[-1]] <= x[i]:
dq.pop()
# Step 4: 加入当前索引 i
dq.append(i)
# Step 5: 队首即为窗口 [left, i] 中最大值的最左索引
result.append(dq[0])
return result
# 测试样例
x = [1000, 4, 3, 2, 500, 10, 1]
k = [1, 2, 2, 3, 2, 3, 1]
print(sliding_max_indices(x, k)) # 输出: [0, 0, 1, 1, 4, 4, 6]? 为什么是 Θ(n)？
- 每个索引 i 最多入队 1 次、出队 1 次（无论 popleft 还是 pop），总操作数 ≤ 2n；
- left 边界随 i 推进单调不减（由 k[i+1] ≤ k[i]+1 保证 left[i+1] ≥ left[i]−1，实际中 left 整体趋势右移），故过期检查均摊 O(1)；
- 无嵌套循环，无 max() 调用，彻底摆脱 O(n·k)。
❌ 为什么不推荐线段树或 Sparse Table？
虽然线段树可将单次 RMQ 降至 O(log n)，但本题 k[i] 变化有强约束，且需返回索引（非仅值）；更重要的是，线段树建树 O(n)，总查询 O(n log n)，劣于单调 deque 的严格 Θ(n)。Sparse Table 同理，预处理 O(n log n)，且不支持动态窗口左边界。
✅ 总结
- 核心洞察：利用 k 数组的缓变性（k[i+1] ≤ k[i] + 1），使窗口左边界变化平滑，适配单调 deque；
- 关键操作：双端队列维护「值递减、索引递增」的候选者，实时裁剪过期与弱势索引；
- 输出即 dq[0]：因其始终代表当前有效窗口中最大值的最早出现位置（队列中相同值会保留更早索引？不——我们弹出 ≤ x[i]，故相等时旧索引被删，新索引 i 入队，但题例无重复最大值；若需严格最左，应改为
- 实战建议：优先使用单调 deque 解决所有「右端固定、左端缓变」的滑动窗口极值问题，它是理论最优且工程友好的 Θ(n) 解法。
