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

滑动窗口最大值

分析

实现

通过后发现 一个代码样例 和 自己写的差不多，但是性能确强 10 倍

未优化的

function maxSlidingWindow(nums: number[], k: number): number[] {
    let queue = [];
    let ans = [];
    for (let i = 0; i < nums.length; i++) {
        if(queue.length > 0 && queue[0] < i - k + 1) {
            queue.shift();
        }

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

优化后

function maxSlidingWindow(nums: number[], k: number): number[] {
	// 给出具体的类型
    let queue: number[] = [];
    let ans: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        if(queue.length > 0 && queue[0] < i - k + 1) {
            queue.shift();
        }

		// 使用 nums[queue[queue.length-1]] <= nums[i]，当旧数据的值 等于 新数据时也应该删除
        while(queue.length >0 && nums[queue[queue.length-1]] <= nums[i]) {
            queue.pop();
        }
        queue.push(i);
        if (i >= k - 1) {
            ans.push(nums[queue[0]]);
        }
    }
    return ans;
   
};

分析

原因：

1. 类型语法
   1. 这看起来只是 TypeScript 的语法规范，但在底层执行时却大有玄机。 当你写 let queue = [] 时，TS 会默认推断它是一个 any[]（可以装任何东西的数组）。JavaScript 底层的 V8 引擎在遇到这种泛型数组时，会分配更复杂、更慢的内存结构。 而大佬明确告诉了引擎 const q: number[] = []，V8 引擎一看：“哦！这全都是整数！” 它就会立刻开启底层优化，分配一段连续的高速内存（Packed SMI Elements），存取速度会快得多。
2. 算法遗漏
   1. 在 JavaScript 中，数组的 shift() 是非常消耗性能的 $O(M)$ 操作（$M$ 是当前数组的长度）。因为把第一个元素删掉后，后面的所有元素都要在内存里往前挪一个位置。 大佬的代码通过 >= 把没必要的重复元素全杀光了，队列极度精简，shift() 挪动元素的负担小得忽略不计；而自己的代码在遇到连续相同数字时，队列变得很长，shift() 就会非常吃力，导致时间暴涨。