滑动窗口最大值

功能说明

slidingWindowMaximum 返回数组中每个长度为 size 的连续窗口的最大值，结果长度为 n 减 size 加一。实现使用单调递减双端队列保存候选下标，每个元素最多入队和出队一次，因此时间复杂度为 O(n)，优于对每个窗口重新扫描的 O(nk)。常用于指标滑窗峰值、信号处理、时间序列异常检测和图像局部极值。

关键代码

队列中保存的是下标而不是值，便于判断元素是否已经滑出窗口。每步先用队首下标与 index 减 size 比较，把过期元素从头部移除；再从队尾删除所有不大于当前值的下标，保证队列对应值单调递减；最后把当前下标入队。窗口填满后队首即最大值。头部通过 head 指针推进而不是 shift，避免每次移动都复制数组。

使用注意

函数不会修改输入数组，也不会对 NaN 做特殊处理；若数据可能含 NaN，应先清洗，因为 NaN 比较恒为假会破坏单调性。窗口大小大于数组长度时返回空数组，若要返回单个全局最大值需调用方自行处理。队列长度最坏为 size，空间复杂度为 O(k)。对超大数组应关注结果本身的内存占用。

验证方式

测试 size 为 1 时结果等于原数组，size 等于数组长度时只返回一个全局最大值，size 超长时返回空数组。用经典序列验证重叠窗口的淘汰顺序，并测试单调递增、单调递减、全部相等与包含负数的数组。再与暴力双重循环的结果做随机对比，确认下标推进和队尾裁剪逻辑一致，同时覆盖 size 为 0 和负数的异常分支。

代码示例

export function slidingWindowMaximum(values, size) {
  if (!Array.isArray(values)) throw new TypeError("values must be an array");
  if (!Number.isInteger(size) || size <= 0) {
    throw new RangeError("size must be a positive integer");
  }
  if (size > values.length) return [];
  const result = [];
  const deque = [];
  let head = 0;
  for (let index = 0; index < values.length; index += 1) {
    while (head < deque.length && deque[head] <= index - size) head += 1;
    while (deque.length > head && values[deque[deque.length - 1]] <= values[index]) {
      deque.pop();
    }
    deque.push(index);
    if (index >= size - 1) result.push(values[deque[head]]);
  }
  return result;
}

export function maxInEachWindow(values, size) {
  return slidingWindowMaximum(values, size);
}