「单调队列」数据结构解决滑动窗口问题

👇👇关注后回复 “进群” ，拉你进程序员交流群👇👇作者丨labuladong来源丨labuladong一、搭建解题框架这道题不复杂，难点在于如何在O(1)时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。这种问题的一个特殊点在于，「窗口」是不断滑动的，也就是你得动态地计算窗口中的最大值。对于这种动态的场景，很容易得到一个结论：在一堆数字中，已知最值为A，如果给这堆数添加一个数B，那么比较一下A和B就可以立即算出新的最值；但如果减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是A，就需要遍历所有数重新找新的最值。回到这道题的场景，每个窗口前进的时候，要添加一个数同时减少一个数，所以想在 O(1) 的时间得出新的最值 ………………………………