给你一组初始事件列表其中每个事件有一个唯一的 eventId 和一个 priority优先级。实现 EventManager 类EventManager(int[][] events) 使用给定事件初始化管理器其中 events[i] [eventIdi, priorityi]。void updatePriority(int eventId, int newPriority) 更新具有 id 为 eventId 的 活跃 事件的优先级为 newPriority。int pollHighest() 移除并返回具有 最高优先级 的 活跃事件 的 eventId。如果有多个活动事件具有相同的优先级则返回 eventId 最小的事件。如果没有活跃事件则返回 -1。如果一个事件没有被 pollHighest() 移除则称其为 活跃事件。示例 1输入[“EventManager”, “pollHighest”, “updatePriority”, “pollHighest”, “pollHighest”][[[[5, 7], [2, 7], [9, 4]]], [], [9, 7], [], []]输出[null, 2, null, 5, 9]解释EventManager eventManager new EventManager([[5,7], [2,7], [9,4]]); // 使用三个事件初始化管理器eventManager.pollHighest(); // 两个事件 5 和 2 的优先级均为 7因此返回 id 最小的事件 2eventManager.updatePriority(9, 7); // 将事件 9 的优先级更新为 7eventManager.pollHighest(); // 剩下的优先级最高的事件是 5 和 9返回 5eventManager.pollHighest(); // 返回 9示例 2输入[“EventManager”, “pollHighest”, “pollHighest”, “pollHighest”][[[[4, 1], [7, 2]]], [], [], []]输出[null, 7, 4, -1]解释EventManager eventManager new EventManager([[4,1], [7,2]]); // 使用两个事件初始化管理器eventManager.pollHighest(); // 返回 7eventManager.pollHighest(); // 返回 4eventManager.pollHighest(); // 没有剩余事件返回 -1提示1 events.length 105^55events[i] [eventId, priority]1 eventId 109^991 priority 109^99events 中的所有 eventId 值都是 唯一的 。1 newPriority 109^99对每次调用 updatePriorityeventId 都指向一个 活跃事件。对 updatePriority 和 pollHighest 的总调用次数最多为 105^55次。懒删除堆我们可以维护一个优先级和事件id的最大堆以及一个事件Id到优先级的哈希表。每次updatePriority时先修改哈希表然后不删除堆中当前事件id的优先级而是插入一个新的正确节点进堆每次pollHighest时检查当前堆顶事件id的优先级是否是哈希表中存放的优先级如果是就找到了优先级最高的事件否则堆顶就是失效的事件classEventManager{public:EventManager(vectorvectorintevents){for(vectorintevent:events){eventToPriority[event[0]]event[1];heap.push_back({event[1],-event[0]});}make_heap(heap.begin(),heap.end());}voidupdatePriority(inteventId,intnewPriority){eventToPriority[eventId]newPriority;heap.push_back({newPriority,-eventId});push_heap(heap.begin(),heap.end());}intpollHighest(){while(!heap.empty()(eventToPriority.find(-heap[0][1])eventToPriority.end()||heap[0][0]!eventToPriority[-heap[0][1]])){pop_heap(heap.begin(),heap.end());heap.pop_back();}if(heap.empty()){return-1;}intans-heap[0][1];pop_heap(heap.begin(),heap.end());heap.pop_back();eventToPriority.erase(ans);returnans;}private:unordered_mapint,inteventToPriority;vectorvectorintheap;};/** * Your EventManager object will be instantiated and called as such: * EventManager* obj new EventManager(events); * obj-updatePriority(eventId,newPriority); * int param_2 obj-pollHighest(); */时间复杂度初始化O(n)其中 n 是 events 的长度。updatePriorityO(log(nq))其中 q 是 updatePriority 的调用次数。pollHighest均摊 O(log(nq))。每个元素至多入堆出堆各一次。空间复杂度O(nq)。