Skip to content

Latest commit

 

History

History
385 lines (328 loc) · 32.4 KB

09.Data Structure.md

File metadata and controls

385 lines (328 loc) · 32.4 KB

第七课：数据结构 Data Structure

常用数据结构方法总结：

队列 queue： BFS的主要数据结构 多做做BFS的题就可以了 
collections.deque() 
append() using append() to insert element at right end   
appendleft() using appendleft() to insert element at left end  
pop() using pop() to delete element from right end  
popleft() using pop() to delete element from left end  
栈 stack：实现：数组//链表  非递归实现DFS的主要数据结构   DFS 的主要数据结构是 Stack 
stack = []  
len(stack)   
append() 跟push()功能差不多   <br>
pop() – Deletes the topmost element of the stack – Time Complexity: O(1) 
实际上用list实现时，这些函数是没有的
push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)   
size() – Returns the size of the stack – Time Complexity: O(1)  
top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)    
Map: Dictionary  
collections.defaultdict(int/list) 
items()	Returns a list containing a tuple for each key value pair  
keys()	Returns a list containing the dictionary's keys  
values()	Returns a list of all the values in the dictionary  
堆 heap:  
1.对已有array堆化: heapify(nums) Time:O(NlogN)  默认小顶堆，每次删除最小的值，所以求第K大的值最简单，heapify没有返回值的.  
2.一个个堆化：q=[] heappush(q, val)   
heappop(nums)       O(logN)   默认小顶堆，pop the smallest value  
heappushpop(a, x)   pushes x onto a before popping the smallest value 
heappush(nums, val) O(logN)  默认小顶堆 
len(nums)  
heapify为tuple时，先按照num1小顶堆，再按照num2小顶堆

Stack栈 and queue队列

Queue implement stack, stack implement queue.

Stack - Parentheses problems, 总结：括号匹配问题，解决思路就是用栈。 分情况讨论时，记住什么时候该出栈

Stack - Decode String

  • 0394.Decode_String.py(!!M Google)
    Solution: 1. we use two stack to seperator number num_st and character str_st, when initialize str_st =[""]. 2.Traverse the array, when we meet digital, get completely digital and then put in num_st. 3. when we meet isalpha(), add all ch into st[-1]. 4.when we meet '(', we need put " " to top stack, because this can seperate diff part, example 3[a]2[b], a and b is diff part, if we donot do that, there will be error. 5. when wen meet ')', we need pop num_st and str_st, get the mutiple str, then add to top stack. Method: The ord() function returns an integer representing the Unicode character.

726（H） 太难了，先不做 solution:类似394题，但是要从后往前遍历遇到数字，找到所有数字，放入num stack中。遇到大写字母判断后面一个数是不是数字，不是数字，对应的个 数就是1.遇到小写字母往前找到大写字母，再入栈。遇到 ） 时，入栈为”“，遇到（时，出栈。”“对应的就是前面原子个数都需要乘上”“对应数字。

Stack - Calculator

  • 0227.Basic_Calculator_II.py(M)
    Solution: the idea is same to 394.用2个栈一个存储num，一个存储operator。遇到乘除法就直接计算，遇到加减法入栈，最后从头遍历栈，得到结果。注意遇到数字要渠道所有的数字。 TODO:224(H) 太难了，先不做

Mono stack

模板：
1.单调递增栈：当num比stack[-1]小的时候，st.pop().更新结果.num入栈。 
2.单调递减：当num比stack[-1]大的时候，st.pop().更新结果.num入栈.每个num都必须入栈，后面可以被pop出来的. 
No matter increasing stack or decreasing stack: 
  1.the key point do we need pop num in current top stack. 
  2. the every num will push to stack.

解题关键：分情况讨论时，记住什么时候该出栈

用于向左/向右寻找第一个比自己大/小的数

  • 0496.Next_Greater_Element_I.py(E)
    单调递减栈，寻找右边第一个比自己大的数.大于栈顶就出栈，小于就入栈. 套用模板即可
  • 0503.Next_Greater_Element_II.py(M)
    单调递减栈，寻找右边一地个比自己大的数。与496不同的是503要先将数组长度扩充成原来的2倍，因为数组元素是可以循环的。
  • 0556.Next_Greater_Element_III.py(M)
    Solutions:跟496和503完全不一样。类似31题(M) solution:1.将整数转成数组 2.从右向左转找到第一个递减的点，记录为left_pos 3.从left_pos出发从左向右找到最后一个将将递增的pos 4.交换2者位置 5.交换后要将left_pos右边的数变成单调递增，才能保证是最小的值。交换后是单调递减的，所以交换变成递增的。6.注意结果不能越界
  • 0739.Daily_Temperatures.py(M)
    solution:套用模板，唯一区别是，栈里要记录下标。
  • 0316.Remove_Duplicate_Letters.py(M)
    Solution: 使用单调递增栈，尽量保证得到的元素是单调递增的，这样才会保证得到的值更小。
    当前元素 > 栈顶元素时(考虑要不要入栈)：
    这个元素是否已经在结果集中了? 在就不入栈,否则入栈.
    当前元素 < 栈顶元素时(考虑要不要入栈，以及要不要pop栈顶)：
    这个元素是否已经在结果集中了? 在就不入栈,否则入栈. （用set记录结果集）
    要不要pop栈顶？看当前栈顶位置是不是已经是该元素最后一个位置了，是就不出栈。 （这里要记录元素以及对应的最后一个位置）
  • 0901.Online_Stock_Span.py(M)
    Solution: 单调递减栈，当当前元素大于栈顶元素时，pop出栈，得到下标之差加入x结果集。
  • 0402.Remove_K_Digits.py(M)
    维护一个递增栈，碰到更小的就把前面的删掉，这样排在前面的就都是最小的了

Histogram Problems

  • 0084.Largest_Rectangle_in_Histogram.py(!!H)
    Solution:1.暴力解法：wh，得到所有的矩形的面积，遍历得到最大的值。 2.栈解法：固定h，向左右扩散，向左边如果高度大于等于当前h，就加入这个面积，如果高度小于当前的高度就不加入，那此时的面积就是h(j-i).实现： 右寻找第一个比自己小的位置right_pos, 记录向左寻找第一个比自己小的位置left_pos,用两次单调栈实现，然后再来计算面积。 非单调栈算法：从左向右遍历数组，然后每遍历到一个高度h，向左边找第一个比自己小的的高度在位置i，向右边找第一个比自己小的的高度在位置j， 那此时的面积就是h*(j-i). 这个算法需要向左向右找第一个比自己小的元素，这类问题就要想到用monostack. 通过maintain a monostack,可以很快找到第一个比i小的元素，就是栈中排在i前面的元素，我们需要做的只是向右找了，所以我们向右遍历，每当遇到大于栈顶的值时，直接入栈保持递增stack，如果遇到小于栈顶的值，这时候说明找到了第一个比i（栈顶）小的元素，这时候我们回头且慢莫慌，栈内各个元素依次出栈并回头计算一下面积。
  • 0085.Maximal_Rectangle.py(H)
    Solution:类似84题，trick的地方在于我们要将每一行以及以上的矩阵转成直方图，然后每一行去调用84题代码，然后得到最大面积。转成直方图的方法，如果当前值为0，那么高度为0，如果不为0，高度就为上一层的高度+1. TODO:1504(M).

Pre-caculate 左/右比自己大/小的idx

TODO:907(M)

Get Max Lexicographical Order

Iterator

Iterator: 主程序在next中实现，hasNext()

  • 0900.RLE_Iterator.py(M)
  • 0341.Flatten_Nested_List_Iterator(!!M)
    Solution:flatten nested list iterator,like [1,[2,3]], we use stack, first input all array data to stack. hasnext() method is check the next integer, so if top stack is integer, return True, if top stack is not integer, we need pop flatten it and push back to stack.
  • 0173.Binary_Search_Tree_Iterator(!!M)
    Solution: 1.init(), push all left node in to stack. 2.hasNext() check the stack length. 3.next() pop top stack data if right node is not null, like init() push all left node into stack. 4.finally, we will get an in-order traverse.
  • 0281.Zigzag_Iterator(!!M)
    Solution: 1.init() record idx1 and idx2 and flag to tag, which array we need get from.
  • 0284.Peeking_Iterator.py(!!M)
    define a self.iterator, and a self.next_item to record the top item of the iterator, 相当于提前预支next_item.
  • 0251.Flatten_2D_Vector.py(!!M)
    Solution: init record row and col. 1. hasNext() check the row then check the col, if col over size, reset row+1 col=0. 2. next() return arr[row][col], then col+1.

Queue

双端队列：deque

Hashmap/Dictionary

数组 O(k的size)  支持操作:O(1) Insert / O(1) Find / O(1) Delete  (真的是O(1)吗？key的size有关系)

Hash Function 使命:对于任意的key 得到一个固定且无规律的介于0~capacity-1的整数
著名的hash算法：MD5, SHA-1, SHA-2
Hash Table:线程安全的hash，同时做好几件事情，都不会崩掉
Hash Map:存key-value
Hash Set:只存key
存在冲突的两种解决办法：Open Hashing（占用别人的位置） vs Closed Hashing（链表连起来）
hash不够大时：Rehashing   <br>
 
解题思路：将list作为key放入dict会报错!解决办法：讲list转成tuple，在使用map.将什么定义成key?
什么能区分不同的group, 就将什么定义成key.
  • 0049.Group_Anagrams.py (!!M)
    Solution: Anagrams is a group of string, like eat, ate, tea. First list all data in array, then list all character in string, sorted, finally use hashmap to group it.
  • 0249.Group_Shifted_Strings.py (!!M Google)
    Solution: record every string shift value, which is the distance to arr[0]. Then group it. ord('0') is the 0 ascii value/
  • 0366.Find_Leaves_of_Binary_Tree.py (!!M)
    将leaf node的level定义为0，临接的node的level定义为1，使用dfs遍历tree，得到所有结点的level，将level，num存入dict中， 就可以得到结果
  • 0166.Fraction_to_Recurring_Decimal.py (!!M)
    166:思路很秒，将reminder, pos存入dict中，每次做除法之前在dict中查找是否已经有了，如果有直接取出pos到当前pos，然后退出。 如果没有如果reminder == 0 退出，否则一直做除法。
  • 0652.Find_Duplicate_Subtrees.py (M)
    Solution: 将树的子树都序列化后存入hashmap, 如果hashmap的value长度大于1说明有相同的子树。注意序列化时 # 代表空， ’，‘一定要隔开左右子树。序列化顺序是：root，root.left，root.right.
  • 1296.Divide_Array_in_Sets_of_K_Consecutive_Numbers.py (M)
    Solution: 先将数组排序，在用Counter得到每个num的频率，从头到尾进行遍历k个，如果连续的k个之中有了一个频率是0，就return false.
  • 0659.Split_Array_into_Consecutive_Subsequences.py (M)
    Solution: 这道题我们遍历nums的时候只要当前的num被前面的顺子需要，就把num连上去，顺子连得越长越好。greedy所在使用2个hashmap，第一个用来建立数字和次数的映射.第二个用来建立数字是否可以被前面顺子所需要。
  • 0706.Design_HashMap.py (E)
    新建一个class用于存储key, value, 以及next, 链表。
  • 0957.Prison_Cells_After_N_Days.py (M)
    找出重复的pattern
  • 0299.Bulls_and_Cows.py (!!!M Google)
    use a digit_to_cnt hashmap for digit. one pass to update A_cnt, another pass to update B_cnt.
  • 0129.Rehashing (lintcode)
  • 0138.Subarray Sum (lintcode)
    复习这2个！！
  • 0138.Copy List with Random Pointer
    Solution 1 O(N), O(N): Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, make sure you are not making multiple copies of the same node. we can use extra space to keep old node --> new node mapping to prevent creating multiples copies of same node.
  • 0242.Valid Anagram
    string s and t are anagram with each other when all the ch in s have the same count as that in t. Counter(s) and Counter(t)
  • 0128.Longest Consecutive Sequence
    使用一个集合hashset存入所有的数字，然后遍历数组中的每个数字，如果其在集合中存在，那就将其移除，然后分别用两个变量prev和next算出其前一个跟后一个数。注意：找到后要删除set中的数，因为没有必要再重复的寻找最大的连续序列，例如4231，找了4的最大连续序列，就不用再找了
  • 0953.Verifying_an_Alien_Dictionary (!!M Facebook)
    hashmap存 the position of ch in the list（idx, character）. we traverse the words list and check adjacent word.
  • 0535.Encode_and_Decode_TinyURL.py (M Google)
    Convert long url to short url via hashing. Look up long url from short url in hash table. # hash(str) returns the hash_code for the str.用一个mapping去存储长短连接之间的对应关系，长短连接的转换用hash去做。hash(str) returns the hash_code for the str.注意hash(str)返回的结果是int
  • 1146.Snapshot_Array.py (!!!!!!!M Google)
    store data snapshot, first we need a array to store the snapshot, and we need a dict to store data.
  • 1400.Construct_K_Palindrome_Strings.py (!!M)
    It is a trick algoritm: we only need to count the sum of number which has odd cnt. Ex. a=3，b=5, so k >= 2 because last a and b can not exist in same palindrome
  • 1170.Compare_Strings_by_Frequency_of_the_Smallest_Character.py (M Google)
    hashmap. step 1: calculate the f(q) for each q in queries f_q, and f(w) for each w in words f_w. step 2: sort the f_w. step 3: ieterate queries and do binary search in f_w to update res.
  • 0036.Valid_Sudoku.py (M)
    use a row_dict to record each row, a col_dict to record each col; a block_dict to record each 3x3 block. block_id is (row // 3, col // 3)
  • 0811.Subdomain_Visit_Count.py (M)
    用一个hashmap存sub-domains --> cnt. 剩下的就是string processing了

OrderedDict用法:

  1. 使用queue去存储最近访问过的key 2. cache去存储key, value 3. get后要更新q 4. put时如果capacity已经不足，要删除最近最久没使用的值
  • 0460.LFU_Cache.py (H)
    1.好的思路是用2个dict去存，key->freq and freq -> (key, value),以及要存储最小频率.因为我们既要根据key查freq,又要根据freq查key,注意题目中很多细节问题 所有的操作都是围绕：1. update key_to_freq 2. update freq_to_orddict 3. update min_freq if needed TODO:895(H)

Hashset

  • 0705.Design_HashSet.py (E)
    Solution: 要使得效率高也要使用hash的方法：同706hashmap的实现一样.ListNode类，key记录data，next记录下一个data的指针。
  • 0562.Longest_Line_of_Consecutive_One_in_Matrix.py (!!M Google)
  • 0202.Happy_Number.py (M)
    solution 1: 用一个hashset记录number, if next number is in visited, 说明成环了，就return False - O(N), O(N); solution 2: slow, fast双指针往前跑，fast跑两步，如果slow == fast说明成环了，return False - O(N), O(1).

hashset. each time we meet a 1, we explore horizontally, vertically and diagonally. Use set to store the nodes that were horizontally visited, vertically visited and diagonally visited. TODO:710(H)

堆 heap & PriorityQueue

实际上是二叉树，实现时可以用数组去存储, sink down, swimm up

  • 支持操作: 堆支持快速的删除任意一个节点
  • O(log N) Add：插入在堆的最右边最下层的位置，然后不断的向上调整，所以是logN
  • O(log N) Remove：需要在logn时删除，需要hashmap，key存储区别每个节点的值，value是在堆里的位置，需要先知道位置后，才能快速删除：将在堆的最右边最下层的位置的值和最顶上的值交换，然后最顶上的值像下调整，与两个儿子中最小的交换
  • O(1) Min or Max Max Heap vs Min Heap : 因为顶上的点就是最小值

Java Version:

  • PriorityQueue（Java-从小到大） vs Heap关系：
  • PriorityQueue是用heap实现的，heap是数据结构角度说的名词，PriorityQueue是从类的角度说的，包装好了一个工具，本质是一个堆。但是没有实现堆的所有功能。
  • PriorityQueue一定要用这个数据结构，面试会考，不是Queue，只是具有Q的接口.
  • priorityQueue的方法有：
    • 删除操作会循环一遍，所以是O(n) delete()//remove()区别于pop()
    • 取heap的大小：size()
    • 插入heap：offer()
    • 取heap顶部元素：peek()
    • 取heap顶部元素：poll()

priorityQueue中为HashMap元素，怎么根据map的value进行排序？
生成小顶堆：Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对） PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a,b) -> a.getValue()==b.getValue() ? a.getKey().compareTo(b.getKey()) : a.getValue()-b.getValue());

Heapify and Heap Sort

  • 把一个数组变成堆:很随意的二叉树变成堆的样子:小的在上面，全局最上面为最小的 时间复杂度：O(N) // O(NlogN)
  • heapify是堆排序的一个步骤，heapify是建立堆的过程. heapify时间复杂度O(n)
  • 堆排序是：建立堆+排序
  • 堆排序时间复杂度是：O(n + nlogn) = nlogn

PriorityQueue

Heapq的应用：
1.Top K problem - top K largest/smallest/frequent
2.Data stream - dynamic situations where large numbers of insertion/remove/query the maximum/minimum operations are intermixed
3.Best first search in graph - Dijkstra’s and A*

Heapq1应用：Top K problem - top K largest/smallest/frequent 1.nlogn方法：适合求Kth largest number 根据num初始化小顶堆，pop出n-k O(nlogn) 根据-num初始化大顶堆，get 0-n-1个元素 (nlogn) 初始化最小堆，pop出K个 klogn 2.nlogK方法：可以有序输出所有topK largest number. K个最大的 先push，如果>k，pop出最小的，复杂度：(n-k)logk K个最小的 -num，进行堆化，先push再出

  • 0130.Heapify.java (M)
  • 0703.Kth Largest Element in a Stream (E)
    maintain a min heap with k size. when initialize, we need heapify it and keep a k size. Then add it, keep a k size. Always Error: heapify(nums), heappop(nums), heappush(nums, val)
  • 0215.Kth Largest Element in an Array (!!!M)
    maintain a min heap with k size.Directly use heapify(num).then pop(). time: O(NlogN + (N-K)logN), N 来自于for循环，logK来自于heap的长度是K，heap 的push 和pop都是logN heapq适合做第K大，第K小，前K大，前K小问题"""
  • 0347.Top K Frequent Elements(!!M)
    K frequent element: need a min heap and size is k, if size larger than k, pop from heap. heappop() vs heappushpop(), heappop() delete the min value. heappushpop() insert a val before delete the min val.
  • 0692.Top_K_Frequent_Words(!!M)
    solution same as 347，the only diff is K sort base on character when count same.
  • 0973.K_Closest_Points_to_Origin(M)
    Heapify (dis, point), then heapify, get k result.
  • 0658.Find_K_Closest_Elements(M)
    Heapify base on distance, and pop k num, and sort result array.
  • 1167.Minimum_Cost_to_Connect_Sticks.py(M)
    我们需要实时地保证选出两个数是最小的, heappop可以保证这一点，所以用heapq

Top K problem - Merge k Sorted Lists

  • 0023.Merge_k_Sorted_Lists(!!H)
    solution1：放入一个数组，然后排序 NlogN N为个数. solution2：heap做 NlogK N为元素个数，heap排序 O(log N),也可以用于array的合并. time:nklogk space:k. First put all head to heap, Then pop the min value. if min value next not in heap, put it in heap. 注意：lt()方法重写，用于比较listnode. ListNode.__lt = __lt def lt(self, other). solution3: divide and conque
  • 0378.Kth_Smallest_Element_in_a_Sorted_Matrix(!!M)
  • solution 1.brute force 变成1D, 排序 ->N^2*logN
  • solution 2.将2d变成1d, 参考0215 ->N^2*logK 比方法1小一点
  • solution 3. 对于任意一个位置(i,j),我们知道(1+1，j),(i, j + 1) 一定比当前数大，展开搜索BFS.起点：(0,0) 每次展开最小值. 利用sorted matrix的性质，从左上角第一个元素开始，添加进heap，然后heap当然自动排序了，然后pop出最小的，然后把最小 的那个数的右边和下边的元素分别入heap，这样可以保证每次pop出来的都是最小的。一定要用set去重。
  • 0373.Find_K_Pairs_with_Smallest_Sums.py(!!M)
    heap solution: klogk, very simlilar with merge k sorted list. 方法二：将两个list各挑一个数出来的加和做成一个2D Array, 由于两个list都是sorted, 那么这个2D array就是与378同样sorted array了, 然后按照378那样解就可以了。
  • 1423.Maximum_Points_You_Can_Obtain_from_Cards.py(E)
    Each time you only can get a num from the beginning or the ending.Solution: calculation the splipper window, size is n-k, get the minum value, so we can get maximum score.follow up要用heap
  • 1086.High_Five(M)
    按照学号统计学生的成绩，边统计边入dict, value存储heapify的成绩，长度大于5时，就pop

Top K problem - Task Schedule

  • Task schedule问题，都是task schedule的做法.用一个hq报错最大的freq，然后按要求排座位，注意add_back.Task schedule每次都是优先排最大的freq 的做法很greedy. heapq 本身就是greedy, 每次都有选择性地pop出来.= dequeue
  • 0621.Task_Scheduler(!!M)
    根据频率得到最大堆maxHeap，q用于存储（-cnt, idleTime), pop后判断count个数，然后将（count，time）入栈。将q中time等于当前时间的入heap.
  • 0767.Reorganize_String.py(!!M)
    跟621很像，唯一的区别是:在每次for循环里面要判断是否hq==0 and backadd > 0 return ""
  • 358 (H)
  • 1405 问一下

Dynamic insert/remove/query the maximum/minimum in Data Stream\

  • 0295.Find_Median_from_Data_Stream(!!H)
    定义两个heap: self.leftHq as a maxheap to store the nums that are smaller than median; and self.rightHq as a minheap store the nums that are larger then median. 每次新增一个数num的时候，先根据比 maxheap 中最后一个数大还是小丢到对应的 heap 里。丢完以后，再处理左右两边的平衡性:如果左边太少了，就从右边拿出一个最小的丢到左边。如果右边太少了，从左边拿出一个最大的丢到右边。时间复杂度是O(logN). Follow up questions are important. Follow up: leetcode 1093.

Greedy 1642(H)

SortedList - Could it be an even stronger heapq?

  • 0480.Sliding_Window_Median(!!H)
    Solution 1: maitain a sorted window. We can use binary search for remove and indert. the overall time complexity is O(NK). similar with 295, we need to maintain two heaps in the window, leftHq and rightHq. To slide one step is actually to do two things: step 1. add a number, which is exactly the same as that in 295. add a number in heapq could be heapq.heappush() which is O(logn) step 2. remove the number that is outside the window; there is not a remmove method in heapq.

Trapping Rain Water

  • 0042.Trapping_Rain_Water(!!H)
    首先找到最高highestBar的位置。然后从左边往最高的位置扫，同时maintain一个指针记录leftHighest的高度，如果扫到的地方i小于这个leftHighest的高度， 则说明i这个地方可以蓄水，可蓄水量为leftHighest的高度减去i的高度；如果扫到的地方i大于这个leftHighest的高度，则说明i这个地方不可以蓄水，所以这时候要更新leftHighest为i的高度。同理对右边做同样的操作
  • 0407.Trapping_Rain_Water_II.py(!!H)
    Similar with 42. 1D trapping rain water. 1D trapping rain water 是用双指针，一个指针记录左边漏水或储水的可能情况，一个指针记录右边漏水或储水的可能情况。 Step 1: store all the outliners of the matrix in heapq. Maintain a visited set to mark all the visited locations. Step 2: starting from the min height position, do BFS the 4 possible moves. If found a height < the min Height, then we can store water, else we cannot store water and we should update this leaking point by putting the new height into the heapq

Ugly Number-heap应用

  • 0263.Ugly_Number.py(E)
    An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.solution:不断的除去直到==1
  • 0264.Ugly_Number_II.py(M) 相当于BFS的解法
    使用heap，先放入1，每次pop出最小值min_val之后，再放入min_val * [2,3,5].千万记得要用set去重
  • 0313.Super_Ugly_Number(M)
    第 264 题的方法包括最小堆和动态规划。由于这道题的数据规模较大，因此最小堆的解法会超时，此处只提供动态规划的解法。
    解法1：最小堆 维护min{dp[i] * 2, dp[j] * 3, dp[k] * 5...} 超时
    解法2：动态规划 TODO：

TreeMap

又想知道最小值，又想支持修改和删除. https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html http://www.lintcode.com/problem/building-outline/