1、滑动窗口和单调栈

滑动窗口是什么？
滑动窗口是一种想象出来的数据结构，窗口有左边界L和右边界R。在数组或者字符串或者一个序列上，记为S，窗口就是S[L…R]这一部分。L往右滑意味着一个样本出窗口，R往右滑意味着一个样本进窗口，L和R都只能往右滑。

假设一个固定大小为W的窗口，一次划过arr
返回每一次滑出状况的最大值
比如：arr=[4,3,5,4,3,3,6,7]，W=3，返回：[5,5,5,4,6,7]

给定一个整型数组arr，和一个整数num
某个arr中的连续子数组sub，如果想达标必须满足：
sub中最大值-sub中最小值<=num
返回arr中达标子数组的数量

单调栈问题
给定一个数组arr，返回每一个位置上的数，
左边离它最小的数的位置，和又边离它最小的数的位置

2、KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

给定两个二叉树big和small，big做头节点的树，是否有某颗子树的结构，和small做头节点的树结构是完全一样的

暴力递归：

KMP算法：

3、Morris遍历

当前节点cur，一开始cur来到整棵树头
1）cur无左树，cur=cur.right
2）cur有左树，找到左树最右节点mostRight
1> mostRight.right==null，则将mostRight.right=cur，cur=cur.left
2> mostRight.right==cur，则将mostRight.right=null，cur=cur.right
3）当cur=null时，整个流程停止
有左树的节点必经历2次，无左树的节点只经历1次

利用Mirros遍历实现二叉树中序遍历

利用Mirros遍历实现二叉树先序遍历

利用Mirros遍历实现二叉树后序遍历

利用Morris遍历判断一棵树是不是搜索二叉树（中序遍历出的值顺序递增）

利用Morris遍历查找一颗树的最小高度

4、线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

想象一下标准的俄罗斯方块游戏，X轴是积木最终下落到底的轴线，经过简化可得出规则：
1）只会下落正方形积木；
2）[a,b]->代表一个变成为b的正方形积木，积木左边缘沿着X=a这条线从上方掉落；
3）认为整个X轴都可以能接住积木，也就是说简化版游戏是没有整体的左右边界；
4）没有整体的左右边界，所以简化版游戏不会消除积木，因为不会有哪一层被填满。
给定一个N*2的二维数组矩阵，可以代表N个积木依次掉落，返回每一次掉落之后的最大高度。