中文
devexamples

Sliding Window Maximum

Compute the maximum of every fixed-size window in O(n) using a monotonic deque, with clear handling of invalid sizes.

JavascriptData Integrity

Code

snippet
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);
}

Related Examples