数据流算法题目小结

由于数据是动态的,按照一般的做法,比如遍历,当新数据的加入,处理单个操作的时间复杂度为O(n),这样往往造成TLE

通过使用合理的数据结构来存储,比如堆,能够将时间复杂度降低到 logn

703. 数据流中的第K大元素

这个本质的思想就是通过小根堆来求第K大元素,通过限制堆大小为k,以及判断堆顶元素与新加入元素val大小关系,将时间复杂度降低到logn.

有一点需要注意的就是做pop() 一定要检查堆是否为空。

295. 数据流的中位数

通过使用两个堆,一个小根堆存放序列中较大的一部分元素,大根堆存放较小的一部分元素,可以形象的把这个结构想象成一个沙漏

通过堆顶元素就能够很方便的得到数据流的中位数。

当新元素val加入如何维护堆?

  1. val 先添加到大根堆maxq, 如果maxq.top>minq.top 需要交换两个堆定元素
  2. 始终保持maxq.size()<=minq.size()+1 这样才能通过堆顶来求中位数