TreeMap

基础知识：基于红黑树 (平衡二叉搜索树) 的一种树状 hashmap，增删查改、找求大最小均为 logN 复杂度，Python 当中可以使用 SortedDict 替代；SortedDict 继承了普通的 dict 全部的方法，除此之外还可以 peekitem(k) 来找 key 里面第 k 大的元素，popitem(k) 来删除掉第 k 大的元素，弥补了 Python 自带的 heapq 没法 logN 时间复杂度内删除某个元素的缺陷；最近又在刷一些 hard 题目时候突然发现 TreeMap 简直是个神技，很多用别的数据结构写起来非常麻烦的题目，TreeMap 解决起来易如反掌。

常见题目：

• Leetcode 729 My Calendar I
• Leetcode 981 Time Based Key-Value Store
• Leetcode 846 Hand of Straights
• Leetcode 218 The Skyline Problem
• Leetcode 480。Sliding Window Median (这个题用 TreeMap 超级方便)
• Leetcode 318 Count of Smaller Numbers After Self (这个题线段树、二分索引树、TreeMap 都可以)