数据结构类问题
# 数据结构类问题
针对滑动窗口 + 数据结构类型，大致分为以下几种情况：
- 求范围，比如[x-t, x+t]，转化为
求[x,x+t]中的最小值和在[x-t, x]中求最大值， 则用红黑树、AVL树、BST树、桶排序- 注意，这种情况可以考虑桶排序，桶排序的效率更高
- 求中位数，可用两个堆，中位数左边较小一部分数据使用大顶堆，中位数右边较大一部分数据使用小顶堆
- 求极值，可用单调队列，若是两个极值，可以两个单调队列（一个存放极大值，一个存放极小值，数据两个都要入队）
总结，降低时间复杂度的一个绝招就是增加空间复杂度：利用更好的数据结构。即此类型题目就是对滑动窗口内使用合适的数据结构，提升时间复杂度，从O(n * n) 提升到O(n * lgn) 或 O(n * 1)
# 例题
To be continued...
# 小结
这个类型，核心是考察对数据结构的掌握，对于滑动窗口使用合适的数据结构，利用增大空间来降低时间复杂度。