[!info] related notes 单调队列 滑动窗口

滑动窗口最大值

LeetCode 239：对每个长度为 k 的连续窗口返回最大值，题目保证 1 ≤ k ≤ nums.length。

原性能观察的修正

原记录观察到两段相近代码在提交结果上有约十倍耗时差异，但没有保留输入、引擎版本和重复测量，不能据此确定因果。

TypeScript 的 number[] 标注在编译后被擦除，不会直接要求 V8 使用某种数组存储格式。两段代码真正的运行时差异是队尾比较使用 < 还是 <=：后者删除相等的旧值，可能缩短队列；前者同样正确。重复值分布与执行环境都会影响测量，不能归纳成固定倍数。

头指针实现

队列存候选下标，用 head 表示有效队首；值按严格递减排列。过期下标从队首跳过，被新值支配的候选从队尾删除。

function maxSlidingWindow(nums: number[], k: number): number[] {
    const queue: number[] = [];
    const ans: number[] = [];
    let head = 0;

    for (let i = 0; i < nums.length; i++) {
        while (head < queue.length && queue[head] <= i - k) {
            head++;
        }
        while (head < queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        queue.push(i);
        if (i >= k - 1) ans.push(nums[queue[head]]);
    }
    return ans;
}

每个下标最多入队、移出有效队列一次，时间 O(n)。此简化实现保留过期前缀，辅助数组最坏 O(n)，不是 O(k)；若需要 O(k) 辅助空间，可用循环 deque。返回结果本身还有 O(n - k + 1) 空间。

题目之外调用时应先明确非法 k 的处理契约；本例不承担通用参数校验。