高级数据结构

Union Find

不支持删除操作 提高查找速度，路径压缩

并查集每个元素有一个指向，跟树中每个节点只要一个父亲一样，所以这个就是一棵树！

适用范围： 合并集合， 查询两个点是否在同一个集合

find O(1)，union O(1)

tips:小集合往大集合合并

Trie

特点：

• 每个点都是26叉树
• 有一个虚根root
• 结尾的点做一个leaf 标记

什么时候用trie

• 查前缀
• 一个个字母
• 省空间

例题：

Word Search II

扫描线算法

某个时间点最多的数量

拆解Interval，开始的时候count++，end的时候count—-，找出max的count

例题：

Meeting room

Airplane in the sky

火车轨道