hihoCoder太阁最新面经算法竞赛题解(2) - 程序园
小Hi最近在分析一支股票的价格走势，他需要一个程序来辅助分析。这个程序会接收3种消息（指令）：
价格信息，格式是：P timestamp price；表示这支股票在timestamp时刻价格是price。
删除价格指令，格式是R timestamp；随着时间推移，小Hi会积累越来越多的价格数据。一些老旧的数据会变得不重要。这个指定会删除timestamp以前（包括timestamp时刻）的价格数据。
价格查询指令，格式是Q：小Hi希望程序返回这只股票最高、最低和最近的价格。注意已经被删除的价格不应该被统计。
给定一个包含以上3种信息（指令）的序列，你能否帮助小Hi完成这个程序呢？
解答：
本题比较简单，是堆和队列的应用，通过建立大顶堆和小顶堆来完成最高股票价格和最低股票价格的实时存储，由于输入是按照时间顺序递增的，所以最近股票价格的信息可以通过队列来维护。因此本题的基本解答步骤是：(1) 初始化大顶堆、小顶堆以及队列。
(2) 根据输入的指令进行操作，如果指令为P，则向堆和队列中添加一条新数据；如果指令为R，则判定队列中队头元素的时间是否小于输入的timestamp，如果小于则出队，同时将两个堆结构中的对应元素也一并删除；如果指令为Q，则最高、最低以及最近的价格分别是当前状态下大顶堆、小顶堆以及队列中的队头元素的值。
Read full article from hihoCoder太阁最新面经算法竞赛题解(2) - 程序园
No comments:
Post a Comment