将O(n*k)子数组最大值索引算法优化为Θ(n)时间复杂度

完全可以用单调队列实现Θ(n)时间复杂度的解法，完美替代O(n*k)的朴素方案，具体思路和步骤如下：

核心逻辑 #

单调队列的作用是维护当前窗口内的候选最大值索引，队列中存储的索引对应的x值单调递减，同时保证所有索引都落在当前i的有效窗口范围（i - k[i] < s ≤ i）内。题目给出的k[i+1] ≤ k[i] + 1约束非常关键：它保证了每个i+1对应的窗口左边界(i+1)-k[i+1]不会比i的窗口左边界i-k[i]更靠左，也就是说窗口左边界只会右移或保持不动，这恰好适配单调队列的处理逻辑，不需要额外的回退操作。

具体实现步骤 #

• 初始化一个双端队列（用于实现单调队列），队列中存储数组索引，队首始终是当前窗口内最大值的索引。
• 遍历每个索引i（从0到n-1）：
  1. 清理无效索引：检查队首元素，如果队首索引≤ i - k[i]，说明它已经不在当前i的有效窗口内，直接弹出队首。
  2. 维护队列单调性：从队尾开始，把所有对应x值小于等于x[i]的索引弹出——这些索引不可能成为后续窗口的最大值，因为当前i的x值更大且位置更靠后，然后将i加入队尾。
  3. 记录结果：此时队首就是当前i对应的子数组中最大值的索引，直接存入结果数组即可。

时间复杂度说明 #

每个索引最多被加入队列一次、弹出一次，所有队列操作的总次数是O(n)，加上遍历数组的O(n)，整体时间复杂度为Θ(n)，完全符合要求。

内容的提问来源于stack exchange，提问作者user23341383