# 第24节 窗口内最大值或最小值的更新结构
# 滑动窗口是什么
滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和有边界R
在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
L和R都只能往右滑
- R++，R向右动，数会从右侧进入窗口
- L++，L向右动，数会从左侧滑出窗口
- 遵循原则，左边界不能跑到右边界的右边去 L <= R
# 滑动内最大值和最小值的更新结构
窗口不管L还是R滑动之后，都会让窗口呈现新状况，
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列(可从头部进，可从头部出，可从尾部进，可从尾部出，而且是O(1)的)
思路：
- 准备数组
[6,4,3,4,5,7,0,5]，准备好双端队列(代表元素从头到尾是由大到小排列)- 窗口新增数时，当有数x滑进窗口时，如R++时，数x由尾部进入队列，双端队列头部代表的值就是窗口内最大值的位置
- 再R++，判断数x是否能落在队列中已有数y的后面(y>x)，若能则从尾部入，不能则从尾部弹出
- 以上是R往右移动时的更新结构
- 窗口减少数时，当有数X滑出窗口时，如L++时，从头部开始看下标有没有过期，若过期则弹出，反之不弹出，双端队列头部代表的值就是窗口内最大值的位置
- 双端队列含义是：如果此时开始窗口缩小的话，哪些位置的数会依次成为窗口内的最大值
双端队列实现更新结构的好处与为什么快？
- 数组中每个位置的数x，最多进入队列一次，出去队列一次，说明当窗口滑动时，队列内部更新的总代价是O(N)，均摊下来的复杂度为O(1)，窗口最大值的位置就是队列的头部元素，查询复杂度为O(1)
# 题目一
假设一个固定大小为W的窗口，依次划过arr， 返回每一次滑出状况的最大值 例如，arr = [4,3,5,4,3,3,6,7], W = 3 返回：[5,5,5,4,6,7]
代码：
1
# 题目二
给定一个整型数组arr，和一个整数num 某个arr中的子数组sub，如果想达标，必须满足： sub中最大值 – sub中最小值 <= num， 返回arr中达标子数组的数量
代码：
1
# 题目三
加油站的良好出发点问题
代码：
1
# 题目四
arr是货币数组，其中的值都是正数。再给定一个正数aim。 每个值都认为是一张货币， 返回组成aim的最少货币数 注意： 因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了
动态规划优化使用了窗口内最大值或最小值的更新结构
代码：
1