数据结构（六）：有序集合
目录
- 很多问题需要维护一个有序的集合，根据操作不同，可以选择更优的数据结构
| 访问 | 搜索 | 插入 | 删除 | 访问最值 | 插入最值 | 删除最值 | |
|---|---|---|---|---|---|---|---|
| 数组 list | O(1) | O(logN) | O(N) | O(N) | O(1) | O(1) | O(1) |
| 队列 deque | O(N) | O(N) | O(N) | O(N) | O(1) | O(1) | O(1) |
| 堆 heapq | O(N) | O(N) | O(logN) | O(N) | O(1) | O(logN) | O(logN) |
| AVL/红黑树 | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) |
- 从表格可知，AVL/红黑树 是一个很平衡的方案，除非要求某项时间 O(1)，否则都是可行的
- python 中可以调用 sortedcontainers.SortedList 得到接近 AVL/红黑树 的效果，其原理是分块+树状数组
sortedlist
- 0220 存在重复元素 III
- 0295 数据流的中位数
- 0352 将数据流变为多个不相交区间
- 0363 矩形区域不超过 K 的最大数值和
- 0480 滑动窗口中位数
- 0683 K 个关闭的灯泡 双有序集合
扫描线
- 0218 天际线问题