左程云P12：进阶的这些知识点就算是被卡车撞了也是不能忘的。

结构一：Dqueue维护窗口的最大值和最小值

题目一：窗口中的最大值最小值更新结构
image.png
image.png
注意：双短队列里面保存的是下标，所以遇到重复的值，可以用后面的索引替换队列尾部的相等值，
如果是存值的话，相等的值就要都加到尾部。
R往右动的时候
image.png
L往右动的时候
image.png

结构二：双端队列

口诀：三山夹两盆
image.png
image.png
image.png
image.png
证明：很简单，看两个结算的元素中间会不会有第三者插足

  • 证明ca的关系
  • 证明ab的关系

image.png
image.png
image.png
有重复的值的情况
image.png
image.png
题目三： 假设数组是正数数组
image.png
image.png

单调栈就两种，要么从小到大， 要么从大到小。
step1 ： 这里要求以每个位置的值为最小值的区间，那么两端比他小的就是不能到达的边界，所以单调栈选用小大小，即从小到大递增的栈顺序。
step2 ： 确定了边界，如何求区间内的和，用前缀和来进行数组的预处理。每个区间的和就是 j位置的前缀和 -i 位置的前缀和。
所以总共的时间复杂度是O(2N)