滑动窗口

3.2 1小时43分

what

1. 滑动窗口结构指的是 有一个序列 定义两个指针L 和 R L<=R L和R会往右移动 用户要求在任一时刻 L到R的窗口范围内序列的最大值

• 上图序列为滑动窗口 我们可以用双端队列来解决这种滑动窗口最值问题
• 双端队列中保存的是数组下标 好处： 信息更多 有下标 根据数组访问有值
• 双端队列的规则如下：

1. 整体要保证 从大到小的顺序 （或从小到大的顺序） 不能相等
2. 当 R 往右移动时 ， 如果新元素小于队尾元素，丢弃。如果大于队尾元素则加入，队尾元素比待加入元素小出队直到可以加入
3. 当 L 往右移动时候，如果队头元素下标跟 L 移动之前元素下标一样的话 队头出队
4. 队列实质上保存的是 当R不动 L移动 滑动窗口内的最大值优先级信息 如下图

练习题

• 见代码

  单调栈

  3.2 2小时10分