介于简单和困难之间的薛定谔算法题？？｜刷题打卡

今天的算法可以说很有意思了，当你用暴力法破解的时候他就是一道简单的题目，而当暴力法一旦被判超时，那难度蹭蹭蹭就上来了，就跟薛定谔的脑血压一样。

一、先看题

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例：

提示：

• 1<=nums.length<=105
• −104<=nums[i]<=104
• 1<=k<=nums.length

原题链接：239. 滑动窗口最大值

二、整理思路

拿到题的第一反应：小样，这还不简单？我TM直接循环拿子数组，然后通过比较取得每个子数组的最大值不就好了？

于是分分钟就写出了答案：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let res=[]
    if(!nums.length) return res 
    for(let i=0;i<nums.length-k+1;i++){
        res.push(Math.max(...nums.slice(i,k+i)))
    }
    return res
};

啪的一下，很快啊，测试用例就通过了，我一个提交甩过去。然后系统不讲武德，一个超时甩我脸上，我当场就懵了。

这时候才注意到，那提示： 1<=nums.length<=105，这么长的数组，暴力法能过就有鬼了。

顿时留下了不学无术的泪水。

经历了 思考 ---> 怀疑人生 ---> 参考答案--->思考。。。的反复循环之后，终于理解了官方题解中的一个解法，贴在下面供大家参考：

var maxSlidingWindow = function (nums, k) {
    //处理空数组
    if(!nums.length) return[]
    //用于存放索引，确保该数组中索引递增，且索引对应的nums元素递增
    let idxArr = []
    //初始化第一个最大值
    for (let i = 0; i < k; i++) {
        while (idxArr.length && nums[i]>=nums[idxArr[idxArr.length-1]]) {
            idxArr.pop();
        }
        idxArr.push(i)
    }
    let res = [nums[idxArr[0]]]
    for(let i=k;i<nums.length;i++){
        while (idxArr.length && nums[i]>=nums[idxArr[idxArr.length-1]]) {
            idxArr.pop();
        }
        idxArr.push(i)
        //及时去除窗口外的数据
        while(idxArr[0]<=i-k){
            idxArr.shift()
        }
        res.push(nums[idxArr[0]])
    }
    return res
}

官方题解还有一个更加高效和厉害的算法，但是我的脑子怎么也没想通到底为什么可以那么做，也贴在这里供大家参考，想要详细讲解的我为你指路原题解！

//本题解是官方第三种题解的浓缩优化版
var maxSlidingWindow = function(nums, k) {
	//空数组处理
    if (!nums.length || !k) return [];
    //p(prefixMax)用于存储前缀，s(suffixMax)用于存储后缀，r(result)用于存储结果
    let n = nums.length, p = new Int16Array(n), 
        s = new Int16Array(n), r = new Int16Array(n - k + 1), i = n, j = -1;
    //最关键的递推思路一直没想通
    while (i--) {
        p[++j] = j % k ? Math.max(p[j - 1], nums[j]) : nums[j]
        s[i]   = i % k ? Math.max(s[i + 1], nums[i]) : nums[i]
    }
    while (i++ < n - k) r[i] = Math.max(s[i], p[i + k - 1])
    return r
}

239. 滑动窗口最大值-官方题解

三、总结

同样一个算法，求解的方式和要求不同，难度就会天差地别，在刷题过程中，我们应该不止要满足测试用例，也要锻炼自己举一反三和思考的能力，力争向最优解靠近，这样才能不断进步！

一起加油吧！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情