Skip to content

Latest commit

 

History

History
229 lines (220 loc) · 62.9 KB

heap-priority-queue.md

File metadata and controls

229 lines (220 loc) · 62.9 KB

堆(优先队列)

全部标签

数据结构

数组 矩阵 链表 双向链表 单调栈 队列 单调队列 堆(优先队列) 哈希表 字符串 字符串匹配 二叉树 二叉搜索树 最小生成树 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程


题号 标题 题解 标签 难度 力扣
23 合并 K 个升序链表 [✓] 链表 分治 堆(优先队列) 1+ 🔴 🀄️ 🔗
215 数组中的第K个最大元素 [✓] 数组 分治 快速选择 2+ 🟠 🀄️ 🔗
218 天际线问题 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
239 滑动窗口最大值 [✓] 队列 数组 滑动窗口 2+ 🔴 🀄️ 🔗
253 会议室 II 🔒 贪心 数组 双指针 3+ 🟠 🀄️ 🔗
264 丑数 II [✓] 哈希表 数学 动态规划 1+ 🟠 🀄️ 🔗
272 最接近的二叉搜索树值 II 🔒 深度优先搜索 4+ 🔴 🀄️ 🔗
295 数据流的中位数 [✓] 设计 双指针 数据流 2+ 🔴 🀄️ 🔗
347 前 K 个高频元素 [✓] 数组 哈希表 分治 5+ 🟠 🀄️ 🔗
355 设计推特 [✓] 设计 哈希表 链表 1+ 🟠 🀄️ 🔗
358 K 距离间隔重排字符串 🔒 贪心 哈希表 字符串 3+ 🔴 🀄️ 🔗
373 查找和最小的 K 对数字 [✓] 数组 堆(优先队列) 🟠 🀄️ 🔗
378 有序矩阵中第 K 小的元素 [✓] 数组 二分查找 矩阵 2+ 🟠 🀄️ 🔗
407 接雨水 II [✓] 广度优先搜索 数组 矩阵 1+ 🔴 🀄️ 🔗
420 强密码检验器 贪心 字符串 堆(优先队列) 🔴 🀄️ 🔗
451 根据字符出现频率排序 [✓] 哈希表 字符串 桶排序 3+ 🟠 🀄️ 🔗
480 滑动窗口中位数 数组 哈希表 滑动窗口 1+ 🔴 🀄️ 🔗
499 迷宫 III 🔒 深度优先搜索 广度优先搜索 5+ 🔴 🀄️ 🔗
502 IPO [✓] 贪心 数组 排序 1+ 🔴 🀄️ 🔗
505 迷宫 II 🔒 深度优先搜索 广度优先搜索 4+ 🟠 🀄️ 🔗
506 相对名次 [✓] 数组 排序 堆(优先队列) 🟢 🀄️ 🔗
621 任务调度器 贪心 数组 哈希表 3+ 🟠 🀄️ 🔗
630 课程表 III 贪心 数组 排序 1+ 🔴 🀄️ 🔗
632 最小区间 [✓] 贪心 数组 哈希表 3+ 🔴 🀄️ 🔗
642 设计搜索自动补全系统 🔒 深度优先搜索 设计 字典树 4+ 🔴 🀄️ 🔗
658 找到 K 个最接近的元素 [✓] 数组 双指针 二分查找 3+ 🟠 🀄️ 🔗
659 分割数组为连续子序列 贪心 数组 哈希表 1+ 🟠 🀄️ 🔗
675 为高尔夫比赛砍树 广度优先搜索 数组 矩阵 1+ 🔴 🀄️ 🔗
683 K 个关闭的灯泡 🔒 树状数组 线段树 队列 5+ 🔴 🀄️ 🔗
692 前K个高频单词 字典树 哈希表 字符串 4+ 🟠 🀄️ 🔗
703 数据流中的第 K 大元素 [✓] 设计 二叉搜索树 3+ 🟢 🀄️ 🔗
743 网络延迟时间 深度优先搜索 广度优先搜索 2+ 🟠 🀄️ 🔗
759 员工空闲时间 🔒 数组 排序 堆(优先队列) 🔴 🀄️ 🔗
767 重构字符串 贪心 哈希表 字符串 3+ 🟠 🀄️ 🔗
778 水位上升的泳池中游泳 深度优先搜索 广度优先搜索 并查集 4+ 🔴 🀄️ 🔗
786 第 K 个最小的质数分数 数组 双指针 二分查找 2+ 🟠 🀄️ 🔗
787 K 站中转内最便宜的航班 深度优先搜索 广度优先搜索 3+ 🟠 🀄️ 🔗
855 考场就座 设计 有序集合 堆(优先队列) 🟠 🀄️ 🔗
857 雇佣 K 名工人的最低成本 贪心 数组 排序 1+ 🔴 🀄️ 🔗
862 和至少为 K 的最短子数组 [✓] 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
871 最低加油次数 贪心 数组 动态规划 1+ 🔴 🀄️ 🔗
882 细分图中的可到达节点 最短路 堆(优先队列) 🔴 🀄️ 🔗
912 排序数组 数组 分治 桶排序 5+ 🟠 🀄️ 🔗
973 最接近原点的 K 个点 [✓] 几何 数组 数学 4+ 🟠 🀄️ 🔗
1046 最后一块石头的重量 [✓] 数组 堆(优先队列) 🟢 🀄️ 🔗
1054 距离相等的条形码 贪心 数组 哈希表 3+ 🟠 🀄️ 🔗
1086 前五科的均分 🔒 数组 哈希表 排序 1+ 🟢 🀄️ 🔗
1094 拼车 数组 前缀和 排序 2+ 🟠 🀄️ 🔗
1102 得分最高的路径 🔒 深度优先搜索 广度优先搜索 并查集 4+ 🟠 🀄️ 🔗
1135 最低成本连通所有城市 🔒 并查集 最小生成树 1+ 🟠 🀄️ 🔗
1167 连接木棍的最低费用 🔒 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
1168 水资源分配优化 🔒 并查集 最小生成树 1+ 🔴 🀄️ 🔗
1172 餐盘栈 设计 哈希表 1+ 🔴 🀄️ 🔗
1183 矩阵中 1 的最大数量 🔒 贪心 堆(优先队列) 🔴 🀄️ 🔗
1199 建造街区的最短时间 🔒 贪心 数组 数学 1+ 🔴 🀄️ 🔗
1263 推箱子 广度优先搜索 数组 矩阵 1+ 🔴 🀄️ 🔗
1268 搜索推荐系统 [✓] 字典树 数组 字符串 3+ 🟠 🀄️ 🔗
1337 矩阵中战斗力最弱的 K 行 [✓] 数组 二分查找 矩阵 2+ 🟢 🀄️ 🔗
1338 数组大小减半 贪心 数组 哈希表 2+ 🟠 🀄️ 🔗
1353 最多可以参加的会议数目 贪心 数组 排序 1+ 🟠 🀄️ 🔗
1354 多次求和构造目标数组 数组 堆(优先队列) 🔴 🀄️ 🔗
1368 使网格图至少有一条有效路径的最小代价 广度优先搜索 数组 3+ 🔴 🀄️ 🔗
1383 最大的团队表现值 贪心 数组 排序 1+ 🔴 🀄️ 🔗
1388 3n 块披萨 贪心 数组 动态规划 1+ 🔴 🀄️ 🔗
1405 最长快乐字符串 [✓] 贪心 字符串 堆(优先队列) 🟠 🀄️ 🔗
1424 对角线遍历 II 数组 排序 堆(优先队列) 🟠 🀄️ 🔗
1425 带限制的子序列和 队列 数组 动态规划 3+ 🔴 🀄️ 🔗
1438 绝对差不超过限制的最长连续子数组 队列 数组 有序集合 3+ 🟠 🀄️ 🔗
1439 有序矩阵中的第 k 个最小数组和 数组 二分查找 矩阵 1+ 🔴 🀄️ 🔗
1464 数组中两元素的最大乘积 [✓] 数组 排序 堆(优先队列) 🟢 🀄️ 🔗
1488 避免洪水泛滥 贪心 数组 哈希表 2+ 🟠 🀄️ 🔗
1499 满足不等式的最大值 队列 数组 滑动窗口 2+ 🔴 🀄️ 🔗
1500 设计文件分享系统 🔒 设计 哈希表 数据流 2+ 🟠 🀄️ 🔗
1514 概率最大的路径 数组 最短路 1+ 🟠 🀄️ 🔗
1606 找到处理最多请求的服务器 贪心 数组 有序集合 1+ 🔴 🀄️ 🔗
1631 最小体力消耗路径 深度优先搜索 广度优先搜索 并查集 4+ 🟠 🀄️ 🔗
1642 可以到达的最远建筑 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
1648 销售价值减少的颜色球 贪心 数组 数学 3+ 🟠 🀄️ 🔗
1675 数组的最小偏移量 贪心 数组 有序集合 1+ 🔴 🀄️ 🔗
1686 石子游戏 VI 贪心 数组 数学 3+ 🟠 🀄️ 🔗
1687 从仓库到码头运输箱子 线段树 队列 数组 4+ 🔴 🀄️ 🔗
1696 跳跃游戏 VI 队列 数组 动态规划 2+ 🟠 🀄️ 🔗
1705 吃苹果的最大数目 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
1738 找出第 K 大的异或坐标值 位运算 数组 分治 5+ 🟠 🀄️ 🔗
1753 移除石子的最大得分 贪心 数学 堆(优先队列) 🟠 🀄️ 🔗
1776 车队 II 数组 数学 2+ 🔴 🀄️ 🔗
1786 从第一个节点出发到最后一个节点的受限路径数 拓扑排序 动态规划 2+ 🟠 🀄️ 🔗
1792 最大平均通过率 [✓] 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
1801 积压订单中的订单总数 数组 模拟 堆(优先队列) 🟠 🀄️ 🔗
1810 隐藏网格下的最小消耗路径 🔒 深度优先搜索 广度优先搜索 2+ 🟠 🀄️ 🔗
1825 求出 MK 平均值 设计 队列 数据流 2+ 🔴 🀄️ 🔗
1834 单线程 CPU 数组 排序 堆(优先队列) 🟠 🀄️ 🔗
1845 座位预约管理系统 设计 堆(优先队列) 🟠 🀄️ 🔗
1851 包含每个查询的最小区间 数组 二分查找 排序 2+ 🔴 🀄️ 🔗
1878 矩阵中最大的三个菱形和 数组 数学 矩阵 3+ 🟠 🀄️ 🔗
1882 使用服务器处理任务 数组 堆(优先队列) 🟠 🀄️ 🔗
1912 设计电影租借系统 设计 数组 哈希表 2+ 🔴 🀄️ 🔗
1942 最小未被占据椅子的编号 [✓] 数组 哈希表 堆(优先队列) 🟠 🀄️ 🔗
1962 移除石子使总数最小 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
1985 找出数组中的第 K 大整数 数组 字符串 分治 3+ 🟠 🀄️ 🔗
2015 每段建筑物的平均高度 🔒 贪心 数组 排序 1+ 🟠 🀄️ 🔗
2034 股票价格波动 设计 哈希表 数据流 2+ 🟠 🀄️ 🔗
2054 两个最好的不重叠活动 [✓] 数组 二分查找 动态规划 2+ 🟠 🀄️ 🔗
2093 前往目标城市的最小费用 🔒 最短路 堆(优先队列) 🟠 🀄️ 🔗
2099 找到和最大的长度为 K 的子序列 [✓] 数组 哈希表 排序 1+ 🟢 🀄️ 🔗
2102 序列顺序查询 设计 数据流 有序集合 1+ 🔴 🀄️ 🔗
2146 价格范围内最高排名的 K 样物品 广度优先搜索 数组 矩阵 2+ 🟠 🀄️ 🔗
2163 删除元素后和的最小差值 数组 动态规划 堆(优先队列) 🔴 🀄️ 🔗
2182 构造限制重复的字符串 [✓] 贪心 哈希表 字符串 2+ 🟠 🀄️ 🔗
2208 将数组和减半的最少操作次数 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
2231 按奇偶性交换后的最大数字 [✓] 排序 堆(优先队列) 🟢 🀄️ 🔗
2233 K 次增加后的最大乘积 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
2285 道路的最大总重要性 贪心 排序 1+ 🟠 🀄️ 🔗
2290 到达角落需要移除障碍物的最小数目 [✓] 广度优先搜索 数组 3+ 🔴 🀄️ 🔗
2333 最小差值平方和 贪心 数组 二分查找 2+ 🟠 🀄️ 🔗
2335 装满杯子需要的最短总时长 [✓] 贪心 数组 排序 1+ 🟢 🀄️ 🔗
2336 无限集中的最小数字 [✓] 设计 哈希表 有序集合 1+ 🟠 🀄️ 🔗
2342 数位和相等数对的最大和 [✓] 数组 哈希表 排序 1+ 🟠 🀄️ 🔗
2343 裁剪数字后查询第 K 小的数字 数组 字符串 分治 4+ 🟠 🀄️ 🔗
2344 使数组可以被整除的最少删除次数 数组 数学 数论 2+ 🔴 🀄️ 🔗
2349 设计数字容器系统 [✓] 设计 哈希表 有序集合 1+ 🟠 🀄️ 🔗
2353 设计食物评分系统 设计 哈希表 有序集合 1+ 🟠 🀄️ 🔗
2357 使数组中所有元素都等于零 [✓] 贪心 数组 哈希表 3+ 🟢 🀄️ 🔗
2386 找出数组的第 K 大和 数组 排序 堆(优先队列) 🔴 🀄️ 🔗
2398 预算内的最多机器人数目 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
2402 会议室 III 数组 哈希表 排序 2+ 🔴 🀄️ 🔗
2406 将区间分为最少组数 [✓] 贪心 数组 双指针 3+ 🟠 🀄️ 🔗
2424 最长上传前缀 并查集 设计 树状数组 4+ 🟠 🀄️ 🔗
2454 下一个更大元素 IV 数组 二分查找 3+ 🔴 🀄️ 🔗
2456 最流行的视频创作者 数组 哈希表 字符串 2+ 🟠 🀄️ 🔗
2462 雇佣 K 位工人的总代价 [✓] 数组 双指针 模拟 1+ 🟠 🀄️ 🔗
2473 购买苹果的最低成本 🔒 数组 最短路 1+ 🟠 🀄️ 🔗
2497 图中最大星和 贪心 数组 2+ 🟠 🀄️ 🔗
2500 删除每行中的最大值 数组 矩阵 排序 2+ 🟢 🀄️ 🔗
2503 矩阵查询可获得的最大分数 广度优先搜索 并查集 数组 4+ 🔴 🀄️ 🔗
2512 奖励最顶尖的 K 名学生 [✓] 数组 哈希表 字符串 2+ 🟠 🀄️ 🔗
2530 执行 K 次操作后的最大分数 [✓] 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
2532 过桥的时间 数组 模拟 堆(优先队列) 🔴 🀄️ 🔗
2542 最大子序列的分数 [✓] 贪心 数组 排序 1+ 🟠 🀄️ 🔗
2551 将珠子放入背包中 贪心 数组 排序 1+ 🔴 🀄️ 🔗
2558 从数量最多的堆取走礼物 [✓] 数组 模拟 堆(优先队列) 🟢 🀄️ 🔗
2577 在网格图中访问一个格子的最少时间 [✓] 广度优先搜索 数组 3+ 🔴 🀄️ 🔗
2593 标记所有元素后数组的分数 [✓] 数组 哈希表 排序 2+ 🟠 🀄️ 🔗
2599 使前缀和数组非负 🔒 贪心 数组 堆(优先队列) 🟠 🀄️ 🔗
2611 老鼠和奶酪 贪心 数组 排序 1+ 🟠 🀄️ 🔗
2617 网格图中最少访问的格子数 广度优先搜索 并查集 5+ 🔴 🀄️ 🔗
2642 设计可以求最短路径的图类 设计 最短路 1+ 🔴 🀄️ 🔗
2662 前往目标的最小代价 数组 最短路 1+ 🟠 🀄️ 🔗
2679 矩阵中的和 数组 矩阵 排序 2+ 🟠 🀄️ 🔗
2699 修改图中的边权 最短路 堆(优先队列) 🔴 🀄️ 🔗
2714 找到 K 次跨越的最短路径 🔒 最短路 堆(优先队列) 🔴 🀄️ 🔗
2737 找到最近的标记节点 🔒 数组 最短路 1+ 🟠 🀄️ 🔗
2762 不间断子数组 [✓] 队列 数组 有序集合 3+ 🟠 🀄️ 🔗
2813 子序列最大优雅度 贪心 数组 3+ 🔴 🀄️ 🔗
2931 购买物品的最大开销 贪心 数组 矩阵 2+ 🔴 🀄️ 🔗
2940 找到 Alice 和 Bob 可以相遇的建筑 [✓] 树状数组 线段树 4+ 🔴 🀄️ 🔗
2944 购买水果需要的最少金币数 队列 数组 动态规划 2+ 🟠 🀄️ 🔗
2959 关闭分部的可行集合数目 位运算 枚举 2+ 🔴 🀄️ 🔗
2969 购买水果需要的最少金币数 II 🔒 队列 数组 动态规划 2+ 🔴 🀄️ 🔗
2973 树中每个节点放置的金币数目 深度优先搜索 动态规划 2+ 🔴 🀄️ 🔗
2974 最小数字游戏 数组 排序 模拟 1+ 🟢 🀄️ 🔗
3013 将数组分成最小总代价的子数组 II 数组 哈希表 滑动窗口 1+ 🔴 🀄️ 🔗
3049 标记所有下标的最早秒数 II 贪心 数组 二分查找 1+ 🔴 🀄️ 🔗
3066 超过阈值的最少操作数 II [✓] 数组 模拟 堆(优先队列) 🟠 🀄️ 🔗
3080 执行操作标记数组中的元素 数组 哈希表 排序 2+ 🟠 🀄️ 🔗
3081 替换字符串中的问号使分数最小 贪心 哈希表 字符串 3+ 🟠 🀄️ 🔗
3092 最高频率的 ID 数组 哈希表 有序集合 1+ 🟠 🀄️ 🔗
3112 访问消失节点的最少时间 数组 最短路 1+ 🟠 🀄️ 🔗
3123 最短路径中的边 深度优先搜索 广度优先搜索 2+ 🔴 🀄️ 🔗
3170 删除星号以后字典序最小的字符串 贪心 哈希表 2+ 🟠 🀄️ 🔗
3264 K 次乘运算后的最终数组 I [✓] 数组 数学 模拟 1+ 🟢 🀄️ 🔗
3266 K 次乘运算后的最终数组 II 数组 模拟 堆(优先队列) 🔴 🀄️ 🔗
3275 第 K 近障碍物查询 数组 堆(优先队列) 🟠 🀄️ 🔗
3286 穿越网格图的安全路径 广度优先搜索 数组 3+ 🟠 🀄️ 🔗
3296 移山所需的最少秒数 贪心 数组 数学 2+ 🟠 🀄️ 🔗
3318 计算子数组的 x-sum I [✓] 数组 哈希表 滑动窗口 1+ 🟢 🀄️ 🔗
3321 计算子数组的 x-sum II [✓] 数组 哈希表 滑动窗口 1+ 🔴 🀄️ 🔗
3341 到达最后一个房间的最少时间 I 数组 矩阵 2+ 🟠 🀄️ 🔗
3342 到达最后一个房间的最少时间 II 数组 矩阵 2+ 🟠 🀄️ 🔗
3362 零数组变换 III 贪心 数组 前缀和 2+ 🟠 🀄️ 🔗
3369 设计数组统计跟踪器 🔒 设计 队列 哈希表 4+ 🔴 🀄️ 🔗
3377 使两个整数相等的数位操作 数学 数论 2+ 🟠 🀄️ 🔗
3391 设计一个高效的层跟踪三维二进制矩阵 🔒 设计 数组 哈希表 3+ 🟠 🀄️ 🔗
3408 设计任务管理器 设计 哈希表 有序集合 1+ 🟠 🀄️ 🔗
3422 将子数组元素变为相等所需的最小操作数 🔒 数组 哈希表 数学 2+ 🟠 🀄️ 🔗
3462 提取至多 K 个元素的最大总和 贪心 数组 矩阵 2+ 🟠 🀄️ 🔗
3476 最大化任务分配的利润 🔒 贪心 数组 排序 1+ 🟠 🀄️ 🔗
3478 选出和最大的 K 个元素 数组 排序 堆(优先队列) 🟠 🀄️ 🔗
LCP 24 数字游戏 数组 数学 堆(优先队列) 🔴 🀄️
LCP 30 魔塔游戏 贪心 数组 堆(优先队列) 🟠 🀄️
LCP 32 批量处理任务 贪心 数组 堆(优先队列) 🔴 🀄️
LCP 33 蓄水 贪心 数组 堆(优先队列) 🟢 🀄️
LCP 35 电动车游城市 最短路 堆(优先队列) 🔴 🀄️
LCP 49 环形闯关游戏 位运算 并查集 数组 1+ 🔴 🀄️
LCP 56 信物传送 广度优先搜索 数组 3+ 🟠 🀄️
剑指 Offer 40 最小的k个数 [✓] 数组 分治 快速选择 2+ 🟢 🀄️
剑指 Offer 41 数据流中的中位数 [✓] 设计 双指针 数据流 2+ 🔴 🀄️
剑指 Offer 49 丑数 [✓] 哈希表 数学 动态规划 1+ 🟠 🀄️
剑指 Offer 59 滑动窗口的最大值 [✓] 队列 数组 滑动窗口 2+ 🔴 🀄️
剑指 Offer II 59 数据流的第 K 大数值 [✓] 设计 二叉搜索树 3+ 🟢 🀄️
剑指 Offer II 60 出现频率最高的 k 个数字 [✓] 数组 哈希表 分治 5+ 🟠 🀄️
剑指 Offer II 61 和最小的 k 个数对 [✓] 数组 堆(优先队列) 🟠 🀄️
剑指 Offer II 76 数组中的第 k 大的数字 [✓] 数组 分治 快速选择 2+ 🟠 🀄️
剑指 Offer II 78 合并排序链表 [✓] 链表 分治 堆(优先队列) 1+ 🔴 🀄️
面试题 17.09 第 k 个数 哈希表 数学 动态规划 1+ 🟠 🀄️
面试题 17.14 最小K个数 数组 分治 快速选择 2+ 🟠 🀄️
面试题 17.20 连续中值 设计 双指针 数据流 2+ 🔴 🀄️