北京
在面试中，你可以这样解释：“对于大小为k的每个窗口，遍历所有元素，找到最大值。”这种暴力方法最直接的代价是，每个窗口都被完整扫描，很多元素被反复处理。时间复杂度O(N×K)，空间复杂度O(1)的代码虽然能跑，但在大数据量下明显吃力。
真正的问题藏在窗口滑动的细节里：每次移动，只有一个元素离开，一个新元素进入。那还有必要把整个窗口的最大值重新算一遍吗？答案是不需要。只要保留那些有资格成为未来最大值的“候选人”，把已经没可能的清除，就能在常数时间内拿到答案。单调队列正是为此而生。
这里的关键观察是，用一个双端队列维护索引，让队列中的元素始终保持递减顺序。这样，队首永远指向当前窗口的最大值。当一个新元素到来时，从队尾把比它小的所有元素索引都删掉——因为它们不可能是之后任何窗口的最大值。同时，把已经滑出窗口的索引从队首移除。
最优解法的四步走非常清晰：第一，检查队首索引是否小于等于i-k，是的话就出队，意味着这个索引已经不属于当前窗口。第二，循环检查队尾索引对应的元素是否小于等于当前元素nums[i]，是的话就弹出队尾，因为小元素没有存留价值。第三，将当前索引i加到队尾。第四，当窗口长度达到k，即i >= k-1时，队首索引对应的元素就是该窗口的最大值，放入结果数组。
以数组[1,3,-1,-3,5,3,6,7]和k=3为例走一遍。初始处理索引0（值1）入队。索引1（值3）进来时，队尾的1小于3，被移出，然后3入队。索引2（值-1）直接入队，此时窗口形成，队首对应值3，第一个最大值3。下一滑动，索引3（值-3）入队前，队首索引0虽然早被移出，但队首已变成索引1，仍在窗口内，所以不移除；队尾-1比-3大，保留。-3入队后队首仍是3，最大值仍为3。运行到索引4（值5），此时窗口覆盖[-1,-3,5]。队尾-3、-1依次被5挤出，队列只剩索引4，队首5成为新的最大值。随后依次得到5、6、7，最终输出[3,3,5,5,6,7]。
为什么单调队列这么高效？因为每个索引都只被插入一次、移出一次，所有元素处理次数总量是线性的。队列始终按值递减排列，保证队首就是候选里的最大者。最终，时间复杂度压到O(N)，空间复杂度为O(K)。到面试最后，完全可以用一句话概括：“维护一个单调递减的索引双端队列，让队首始终代表当前滑动窗口的最大元素。”
这个模式一旦内化，只要是“滑动窗口”碰上“最大/最小”的组合，第一时间就应想到单调队列。同类问题还包括：滑动窗口最小值、每个窗口第一个负整数、和至少为K的最短子数组、受限制的子序列和等等。掌握这一手，就能把本来需要重复计算的开销，压缩成一次遍历的精准操作。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
