数据结构

优先队列

原理:基于堆结构实现（大根堆或小根堆），自动对元素进行排序，每次取出堆顶元素（最大或最小元素）。插入和删除操作的时间复杂度均为 O (log n)。

应用:处理需要频繁获取最大或最小元素的问题，如 Dijkstra 算法中用于选取当前距离最小的节点、任务调度问题（每次选取优先级最高的任务）等。

哈希表

原理:过哈希函数将键映射到数组中的某个位置，实现快速的查找、插入和删除操作。哈希函数的设计至关重要，要尽量减少冲突，常用的解决冲突的方法有开放寻址法和链地址法。

应用:快速查找数据（如判断某个元素是否存在于集合中）、统计元素的出现次数（如在 “字母异位词分组” 问题中，用哈希表记录每个字母排序后的字符串对应的分组）等。

并查集

原理:每个集合用一个根节点表示，每个节点存储其父节点，通过路径压缩和按秩合并优化，使得查找和合并操作的时间复杂度接近 O (1)。

应用:解决不相交集的合并

单调栈

原理:栈中的元素保持单调递增或递减的顺序。当新元素入栈时，弹出栈中不满足单调性的元素，直到栈顶元素满足单调性条件，然后将新元素入栈。

应用:求解序列中每个数最左边或最右边第一个大于（或小于）其的数

​ 求解序列中所有子序列的最值和

单调队列

原理:队列中的元素保持单调递增或递减的顺序。当新元素进入队列时，从队列尾部删除比新元素大（或小）的元素，然后将新元素加入队尾；同时，从队列头部删除超出窗口范围的元素。

应用:求解序列中每个长度为 k 的窗口的最值（最大值或最小值）。