)
目录一优先队列二STL优先队列三二叉堆实现优先队列四二项堆实现优先队列五线段树实现优先队列六OJ实战力扣 295. 数据流的中位数力扣 LCP 24. 数字游戏力扣 LCP 30. 魔塔游戏力扣 2462. 雇佣 K 位工人的总代价力扣 632. 最小区间力扣 857. 雇佣 K 名工人的最低成本力扣 1705. 吃苹果的最大数目其他应用一优先队列优先队列可以插入元素、查询最大值、删除最大值。优先队列其实就是最大堆或最小堆最大堆可以用来实现最大优先队列最小堆可以用来实现最小优先队列。用各种堆都可以实现优先队列。二STL优先队列优先队列如果要自定义排序函数只能用仿函数不能用普通函数的指针。示例#includeiostream #includequeue #includefunctional using namespace std; class cmp { public: bool operator()(int a, int b) { return a b; } }; bool cmp2(int a, int b) { return a b; } template typename A void display() { A q; q.push(1); q.push(3); q.push(4); q.push(2); while (!q.empty()) { cout q.top(); q.pop(); } cout endl; } int main() { display priority_queueint, vectorint (); //默认大顶堆 display priority_queue int, vectorint, greaterint ();//小顶堆 display priority_queue int, vectorint, lessint ();//大顶堆 display priority_queueint, vectorint, cmp();//大顶堆 //display priority_queueint, vectorint, cmp2(); 错误 return 0; }输出4321123443214321附上priority_queue的实现代码// TEMPLATE CLASS priority_queue templateclass _Ty, class _Container vector_Ty, class _Pr lesstypename _Container::value_type class priority_queue { // priority queue implemented with a _Container public: ...... 一堆函数 ...... protected: _Container c; // the underlying container _Pr comp; // the comparator functor };可以看出模板参数_Pr的默认值是less也就是说默认排序函数是less函数。priority_queue中包含一个排序的序列堆顶是这个序列的最后一个元素所以从小到大排序是大顶堆从大到小排序是小顶堆。三二叉堆实现优先队列二叉堆最大优先队列#includeiostream #include vector using namespace std; templatetypename T bool cmp(T a, T b) { return a b; //最大堆 } templatetypename T void exchange(T* a, T* b) { T tmp *a; *a *b; *b tmp; } int LeftChild(int id) { return id * 2; } int RightChild(int id) { return id * 2 1; } int Parent(int id) { return id/2; } templatetypename T void AdjustHeap(T* arr, int rootId, int size) { int largest rootId, left LeftChild(rootId), right RightChild(rootId); if (left size cmp(arr[largest], arr[left]))largest left; if (right size cmp(arr[largest], arr[right]))largest right; if (largest rootId)return; exchange(arr rootId, arr largest); AdjustHeap(arr, largest, size); } templatetypename T void HeapIncrese(T* arr, int size, int id, T newValue) { arr[id] newValue; while (id 0 cmp(arr[Parent(id)], arr[id])) { exchange(arr id, arr Parent(id)); id Parent(id); } } templatetypename T void HeapInsert(T* arr, int size,T value) { HeapIncrese(arr,size1,size,value); size; } int g_size; void Init() { g_size 0; } templatetypename T T Top(T* arr) { return arr[0]; } templatetypename T void Push(T* arr, T value) { HeapInsert(arr,g_size,value); } templatetypename T void Pop(T* arr) { g_size--; exchange(arr, arrg_size); AdjustHeap(arr, 0, g_size); } int main() { int q[10]; Init(); Push(q,4); Push(q,2); Push(q,6); Push(q,3); Push(q,4); Push(q,5); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutendlg_size; return 0; }运行结果6 5 4 4 3 20四二项堆实现优先队列二项堆 里面已经实现了push、pop、top等操作所以它就是一种优先队列。五线段树实现优先队列代码struct anode { int t; int d; }; int n; int num[10001],maxx[40001]; struct anode node[10001]; void build(int key, int low, int high)//id { if (low high) { maxx[key] low; return; } int mid (low high) / 2; build(key * 2, low, mid); build(key * 2 1, mid 1, high); maxx[key] (num[maxx[key * 2]] num[maxx[key * 2 1]]) ? maxx[key * 2] : maxx[key * 2 1]; } void update(int key, int low, int high, int uplace)//id { if (low high) { maxx[key] low; return; } int mid (low high) / 2; if (uplace mid)update(key * 2, low, mid, uplace); else update(key * 2 1, mid 1, high, uplace); maxx[key] (num[maxx[key * 2]] num[maxx[key * 2 1]]) ? maxx[key * 2] : maxx[key * 2 1]; } int query(int key, int low, int high, int x, int y)//id { if (low x high y)return maxx[key]; int mid (low high) / 2; if (mid x)return query(key * 2 1, mid 1, high, x, y); if (mid y)return query(key * 2, low, mid, x, y); int a query(key * 2, low, mid, x, mid); int b query(key * 2 1, mid 1, high, mid 1, y); return (num[a]num[b]) ? a : b; } void push(int loc) { num[loc]node[loc].t; ///根据实际情况修改 update(1,1,n,loc); } void pop(int loc) { num[loc]0; ///根据实际情况修改 update(1,1,n,loc); } int top()//id { return query(1,1,n,1,n); }应用力扣 630. 课程表 III六OJ实战力扣 295. 数据流的中位数中位数是有序列表中间的数。如果列表长度是偶数中位数则是中间两个数的平均值。例如[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 3) / 2 2.5设计一个支持以下两种操作的数据结构void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。示例addNum(1)addNum(2)findMedian() - 1.5addNum(3)findMedian() - 2思路维护1个最大堆和1个最小堆并动态维持他们的尺寸相同。class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty()||numqmax.top())qmax.push(num); else qmin.push(num); } double findMedian() { while (qmin.size() qmax.size()) qmax.push(qmin.top()),qmin.pop(); while (qmax.size() qmin.size()1)qmin.push(qmax.top()),qmax.pop(); if (qmax.size() qmin.size())return qmax.top(); return (qmax.top() qmin.top()) / 2.0; } private: priority_queueint, vectorint qmax; priority_queue int, vectorint, greaterint qmin; };或者用自己实现的堆templatetypename T class MyHeap { public: T arr[100000]; MyHeap(int type)//0最小堆1最大堆 { this-type type; } T Top() { return arr[0]; } void Push(T value) { HeapInsert(arr, value); } void Pop() { size--; exchange(arr, arr size); AdjustHeap(arr, 0); } bool empty() { return size 0; } int Size() { return size; } private: void AdjustHeap(T* arr, int rootId) { int largest rootId, left LeftChild(rootId), right RightChild(rootId); if (left size cmp(arr[largest], arr[left]))largest left; if (right size cmp(arr[largest], arr[right]))largest right; if (largest rootId)return; exchange(arr rootId, arr largest); AdjustHeap(arr, largest); } void HeapIncrese(T* arr, int id, T newValue) { arr[id] newValue; while (id 0 cmp(arr[Parent(id)], arr[id])) { exchange(arr id, arr Parent(id)); id Parent(id); } } void HeapDecrese(T* arr, int size, int id, T newValue) { arr[id] newValue; AdjustHeap(arr, id, size); } void HeapChange(T* arr, int id, T newValue) { if (cmp(arr[id], newValue))HeapIncrese(arr, id, newValue); else HeapDecrese(arr, id, newValue); } void HeapInsert(T* arr, T value) { HeapIncrese(arr, size, value); } bool cmp(T a, T b) { return type ? (a b) : (a b); } void exchange(T* a, T* b) { T tmp *a; *a *b; *b tmp; } int LeftChild(int id) { return id * 2 1; } int RightChild(int id) { return id * 2 2; } int Parent(int id) { return (id - 1) / 2; } int type; int size 0; }; class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty() || num qmax.Top())qmax.Push(num); else qmin.Push(num); } double findMedian() { while (qmin.Size() qmax.Size()) qmax.Push(qmin.Top()), qmin.Pop(); while (qmax.Size() qmin.Size() 1)qmin.Push(qmax.Top()), qmax.Pop(); if (qmax.Size() qmin.Size())return qmax.Top(); return (qmax.Top() qmin.Top()) / 2.0; } private: MyHeapint qmax{ 1 }; MyHeapint qmin{ 0 }; };力扣 LCP 24. 数字游戏小扣在秋日市集入口处发现了一个数字游戏。主办方共有N个计数器计数器编号为0 ~ N-1。每个计数器上分别显示了一个数字小扣按计数器编号升序将所显示的数字记于数组nums。每个计数器上有两个按钮分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器按下加一或减一按钮。主办方请小扣回答出一个长度为N的数组第i个元素(0 i N)表示将0~i号计数器初始所示数字操作成满足所有条件nums[a]1 nums[a1],(0 a i)的最小操作数。回答正确方可进入秋日市集。由于答案可能很大请将每个最小操作数对1,000,000,007取余。示例 1输入nums [3,4,5,1,6,7]输出[0,0,0,5,6,7]解释 i 0[3] 无需操作 i 1[3,4] 无需操作 i 2[3,4,5] 无需操作 i 3将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作 i 4将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作 i 5将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]最少 7 次操作 返回 [0,0,0,5,6,7]。示例 2输入nums [1,2,3,4,5]输出[0,0,0,0,0]解释对于任意计数器编号 i 都无需操作。示例 3输入nums [1,1,1,2,3,4]输出[0,1,2,3,3,3]解释 i 0无需操作 i 1将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作 i 2将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]最少 2 次操作 i 3将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]最少 3 次操作 i 4将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]最少 3 次操作 i 5将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]最少 3 次操作 返回 [0,1,2,3,3,3]。提示1 nums.length 10^51 nums[i] 10^3思路把力扣 295. 数据流的中位数中的MedianFinder进行改造数据流的形式不变把查询中位数改成查询所有数到中位数的距离总和。实现的思路不变时间复杂度也不变。利用改造后的MedianFinder直接可以得到本题的答案。class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty() || num qmax.top()) { if (qmax.size() qmin.size()) { qmax.push(num); s qmax.top() - num; } else { qmin.push(qmax.top()), qmax.pop(); qmax.push(num); s qmin.top() - num; } } else { if (qmax.size() qmin.size()) { qmin.push(num); s num - qmin.top(); qmax.push(qmin.top()), qmin.pop(); } else { qmin.push(num); s num - qmax.top(); } } } long long sumLen() { return s; } private: long long s 0; priority_queueint, vectorint qmax;//最大堆放小的一半数据 priority_queue int, vectorint, greaterint qmin;//最小堆放大的一半数据 }; class Solution { public: vectorint numsGame(vectorint nums) { MedianFinder opt; vectorintans; for(int i0;inums.size();i){ opt.addNum(nums[i]-i); ans.push_back(opt.sumLen() % 1000000007); } return ans; } };力扣 LCP 30. 魔塔游戏小扣当前位于魔塔游戏第一层共有N个房间编号为0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组nums其中正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0表示房间对血量无影响。小扣初始血量为 1且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。请返回小扣最少需要调整几次才能顺利访问所有房间。若调整顺序也无法访问完全部房间请返回 -1。示例 1输入nums [100,100,100,-250,-60,-140,-50,-50,100,150]输出1解释初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。示例 2输入nums [-200,-300,400,0]输出-1解释调整访问顺序也无法完成全部房间的访问。提示1 nums.length 10^5-10^5 nums[i] 10^5class Solution { public: int magicTower(vectorint nums) { priority_queueint, vectorintq; long long s 0, s2 0, n 0; for (auto x : nums) { if (x 0)q.push(-x); s x; if (s 0) { s q.top(); s2 q.top(); q.pop(); n; } } if (s - s2 0)return n; return -1; } };力扣 2462. 雇佣 K 位工人的总代价给你一个下标从0开始的整数数组costs其中costs[i]是雇佣第i位工人的代价。同时给你两个整数k和candidates。我们想根据以下规则恰好雇佣k位工人总共进行k轮雇佣且每一轮恰好雇佣一位工人。在每一轮雇佣中从最前面candidates和最后面candidates人中选出代价最小的一位工人如果有多位代价相同且最小的工人选择下标更小的一位工人。比方说costs [3,2,7,7,1,2]且candidates 2第一轮雇佣中我们选择第4位工人因为他的代价最小[3,2,7,7,1,2]。第二轮雇佣我们选择第1位工人因为他们的代价与第4位工人一样都是最小代价而且下标更小[3,2,7,7,2]。注意每一轮雇佣后剩余工人的下标可能会发生变化。如果剩余员工数目不足candidates人那么下一轮雇佣他们中代价最小的一人如果有多位代价相同且最小的工人选择下标更小的一位工人。一位工人只能被选择一次。返回雇佣恰好k位工人的总代价。示例 1输入costs [17,12,10,2,7,2,11,20,8], k 3, candidates 4输出11解释我们总共雇佣 3 位工人。总代价一开始为 0 。 - 第一轮雇佣我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 有两位工人我们选择下标更小的一位工人即第 3 位工人。总代价是 0 2 2 。 - 第二轮雇佣我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 下标为 4 总代价是 2 2 4 。 - 第三轮雇佣我们从 [17,12,10,7,11,20,8] 中选择最小代价是 7 下标为 3 总代价是 4 7 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。 总雇佣代价是 11 。示例 2输入costs [1,2,4,1], k 3, candidates 3输出4解释我们总共雇佣 3 位工人。总代价一开始为 0 。 - 第一轮雇佣我们从 [1,2,4,1] 中选择。最小代价为 1 有两位工人我们选择下标更小的一位工人即第 0 位工人总代价是 0 1 1 。注意下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。 - 第二轮雇佣我们从 [2,4,1] 中选择。最小代价为 1 下标为 2 总代价是 1 1 2 。 - 第三轮雇佣少于 3 位工人我们从剩余工人 [2,4] 中选择。最小代价是 2 下标为 0 。总代价为 2 2 4 。 总雇佣代价是 4 。提示1 costs.length 1051 costs[i] 1051 k, candidates costs.lengthstruct Node { int x, id; }; class cmp { public: bool operator()(Node a, Node b) { if (a.x b.x)return a.id b.id; return a.x b.x; } }; class Solution { public: long long totalCost(vectorint costs, int k, int candidates) { priority_queueNode, vectorNode, cmpq; int low 0, high costs.size() - 1; while (low candidates low costs.size()) { q.push(Node{ costs[low],low }); } while (high costs.size() - candidates high low) { q.push(Node{ costs[high],high-- }); } long long ans 0; while (!q.empty() k--) { Node nod q.top(); q.pop(); ans nod.x; if (low high) { if(nod.idlow)q.push(Node{ costs[low],low }); else q.push(Node{ costs[high],high-- }); } } return ans; } };力扣 632. 最小区间你有k个非递减排列的整数列表。找到一个最小区间使得k个列表中的每个列表至少有一个数包含在其中。我们定义如果b-a d-c或者在b-a d-c时a c则区间[a,b]比[c,d]小。示例 1输入nums [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]输出[20,24]解释列表 1[4, 10, 15, 24, 26]24 在区间 [20,24] 中。 列表 2[0, 9, 12, 20]20 在区间 [20,24] 中。 列表 3[5, 18, 22, 30]22 在区间 [20,24] 中。示例 2输入nums [[1,2,3],[1,2,3],[1,2,3]]输出[1,1]提示nums.length k1 k 35001 nums[i].length 50-105 nums[i][j] 105nums[i]按非递减顺序排列struct Node { int x, id; }; class cmp { public: bool operator()(Node a, Node b) { return a.x b.x; } }; class Solution { public: vectorint smallestRange(vectorvectorint nums) { vectorintids(nums.size(), 0); vectorintans{-100000,100000}; priority_queueNode, vectorNode, cmpq;//最小堆 int minMax 100000; int maxid 0; for (int i 0; i ids.size(); i) { if (nums[i][0] nums[maxid][0])maxid i; minMax min(minMax, nums[i][nums[i].size() - 1]); q.push(Node{ nums[i][0],i }); } while (true) { int t q.top().x; int minid q.top().id; q.pop(); if (ans[1] - ans[0] nums[maxid][ids[maxid]] - nums[minid][ids[minid]] || (ans[1] - ans[0] nums[maxid][ids[maxid]] - nums[minid][ids[minid]] ans[0] nums[minid][ids[minid]])) { ans vectorint{ nums[minid][ids[minid]] ,nums[maxid][ids[maxid]] }; } if (ids[minid] 1 nums[minid].size())return ans; ids[minid]; if (nums[minid][ids[minid]] nums[maxid][ids[maxid]])maxid minid; q.push(Node{ nums[minid][ids[minid]],minid }); } return ans; } };力扣 857. 雇佣 K 名工人的最低成本有n名工人。 给定两个数组quality和wage其中quality[i]表示第i名工人的工作质量其最低期望工资为wage[i]。现在我们想雇佣k名工人组成一个工资组。在雇佣 一组k名工人时我们必须按照下述规则向他们支付工资对工资组中的每名工人应当按其工作质量与同组其他工人的工作质量的比例来支付工资。工资组中的每名工人至少应当得到他们的最低期望工资。给定整数k返回组成满足上述条件的付费群体所需的最小金额。在实际答案的10-5以内的答案将被接受。。示例 1输入quality [10,20,5], wage [70,50,30], k 2输出105.00000解释我们向 0 号工人支付 70向 2 号工人支付 35。示例 2输入quality [3,1,10,10,1], wage [4,8,2,2,7], k 3输出30.66667解释我们向 0 号工人支付 4向 2 号和 3 号分别支付 13.33333。提示n quality.length wage.length1 k n 1041 quality[i], wage[i] 104struct Node { int q, w; }; bool cmp(Node a, Node b) { return a.w * b.q b.w * a.q; } class cmp2 { public: bool operator()(Node a, Node b) { return a.q b.q; } }; class Solution { public: double mincostToHireWorkers(vectorint quality, vectorint wage, int k) { vectorNodev; for (int i 0; i quality.size(); i) { v.push_back(Node{ quality[i],wage[i] }); } sort(v.begin(), v.end(), cmp); priority_queueNode, vectorNode, cmp2q; int s 0; for (int i 0; i k; i) { s v[i].q; q.push(v[i]); } double ans v[k - 1].w * 1.0 / v[k - 1].q * s; for (int i k; i v.size(); i) { s v[i].q; q.push(v[i]); auto nod q.top(); q.pop(); s - nod.q; ans min(ans, v[i].w * 1.0 / v[i].q * s); } return ans; } };力扣 1705. 吃苹果的最大数目有一棵特殊的苹果树一连n天每天都可以长出若干个苹果。在第i天树上会长出apples[i]个苹果这些苹果将会在days[i]天后也就是说第i days[i]天时腐烂变得无法食用。也可能有那么几天树上不会长出新的苹果此时用apples[i] 0且days[i] 0表示。你打算每天最多吃一个苹果来保证营养均衡。注意你可以在这n天之后继续吃苹果。给你两个长度为n的整数数组days和apples返回你可以吃掉的苹果的最大数目。示例 1输入apples [1,2,3,5,2], days [3,2,1,4,2]输出7解释你可以吃掉 7 个苹果 - 第一天你吃掉第一天长出来的苹果。 - 第二天你吃掉一个第二天长出来的苹果。 - 第三天你吃掉一个第二天长出来的苹果。过了这一天第三天长出来的苹果就已经腐烂了。 - 第四天到第七天你吃的都是第四天长出来的苹果。示例 2输入apples [3,0,0,0,0,2], days [3,0,0,0,0,2]输出5解释你可以吃掉 5 个苹果 - 第一天到第三天你吃的都是第一天长出来的苹果。 - 第四天和第五天不吃苹果。 - 第六天和第七天你吃的都是第六天长出来的苹果。提示apples.length ndays.length n1 n 2 * 1040 apples[i], days[i] 2 * 104只有在apples[i] 0时days[i] 0才成立思路直接按照deadline排序做成小顶堆struct Node { int num; int deadline; bool operator(const Node nod)const { return deadline nod.deadline; } }; class Solution { public: int eatenApples(vectorint apples, vectorint days) { priority_queueNode, vectorNode, greaterNodeq; int ans 0; for (int i 0; i days.size() || !q.empty(); i) { if (i days.size() days[i]0) { q.push(Node{ apples[i],days[i] i - 1 }); } while (!q.empty()) { Node nod q.top(); q.pop(); if (nod.deadline i) continue; if (--nod.num 0 nod.deadline i) { q.push(nod); } ans; break; } } return ans; } };力扣 2812. 找出最安全路径给你一个下标从0开始、大小为n x n的二维矩阵grid其中(r, c)表示如果grid[r][c] 1则表示一个存在小偷的单元格如果grid[r][c] 0则表示一个空单元格你最开始位于单元格(0, 0)。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。矩阵中路径的安全系数定义为从路径中任一单元格到矩阵中任一小偷所在单元格的最小曼哈顿距离。返回所有通向单元格(n - 1, n - 1)的路径中的最大安全系数。单元格(r, c)的某个相邻单元格是指在矩阵中存在的(r, c 1)、(r, c - 1)、(r 1, c)和(r - 1, c)之一。两个单元格(a, b)和(x, y)之间的曼哈顿距离等于| a - x | | b - y |其中|val|表示val的绝对值。示例 1输入grid [[1,0,0],[0,0,0],[0,0,1]]输出0解释从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。示例 2输入grid [[0,0,1],[0,0,0],[0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格02最近的单元格是00。它们之间的曼哈顿距离为 | 0 - 0 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。示例 3输入grid [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格03最近的单元格是12。它们之间的曼哈顿距离为 | 0 - 1 | | 3 - 2 | 2 。 - 该路径上距离小偷所在单元格30最近的单元格是32。它们之间的曼哈顿距离为 | 3 - 3 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。提示1 grid.length n 400grid[i].length ngrid[i][j]为0或1grid至少存在一个小偷class Solution { public: int maximumSafenessFactor(vectorvectorint grid) { mapint, intm; setintids; for (int i 0; i grid.size(); i) { for (int j 0; j grid[0].size(); j) { if (grid[i][j] 1) { m[i * grid[0].size() j] 1; ids.insert(i * grid[0].size() j); } } } bfs(ids, grid, m); auto v grid; for (int i 0; i grid.size(); i) { for (int j 0; j grid[0].size(); j) { v[i][j] m[i * grid[0].size() j]; } } return maximumMinimumPath(v)-1; } int maximumMinimumPath(vectorvectorint grid) { int m grid.size(); if (m 0) return 0; int n grid[0].size(); if (n 0) return 0; // 大顶堆优先队列存储 {路径最小值, 行, 列} // C priority_queue 默认是最大堆 priority_queuepairint, pairint, int pq; // 记录节点是否被访问过 vectorvectorbool visited(m, vectorbool(n, false)); // 起点入队 pq.push({ grid[0][0], {0, 0} }); visited[0][0] true; // 上下左右四个方向 int dirs[4][2] { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; while (!pq.empty()) { auto curr pq.top(); pq.pop(); int val curr.first; // 当前路径上的最小值 int r curr.second.first; // 当前行 int c curr.second.second; // 当前列 // 如果已经到达右下角直接返回当前路径的最小值 if (r m - 1 c n - 1) { return val; } // 向四个方向扩展 for (int i 0; i 4; i) { int nr r dirs[i][0]; int nc c dirs[i][1]; // 检查边界和是否访问过 if (nr 0 nr m nc 0 nc n !visited[nr][nc]) { visited[nr][nc] true; // 扩展到邻居节点后路径的最小值为当前 val 和邻居节点值的较小者 int next_val min(val, grid[nr][nc]); pq.push({ next_val, {nr, nc} }); } } } return -1; // 理论上不会执行到这里 } void bfs(setintids, vectorvectorint grid, mapint, intm) { while (m.size() grid.size() * grid[0].size()) { setintnew_ids; for (auto id : ids) { int x id / grid[0].size(); int y id % grid[0].size(); if (x 0 m.find((x - 1) * grid[0].size() y) m.end()) { m[(x - 1) * grid[0].size() y] m[id] 1; new_ids.insert((x - 1) * grid[0].size() y); } if (x grid.size() - 1 m.find((x 1) * grid[0].size() y) m.end()) { m[(x 1) * grid[0].size() y] m[id] 1; new_ids.insert((x 1) * grid[0].size() y); } if (y 0 m.find(x * grid[0].size() (y - 1)) m.end()) { m[x * grid[0].size() (y - 1)] m[id] 1; new_ids.insert(x * grid[0].size() (y - 1)); } if (y grid[0].size() - 1 m.find(x * grid[0].size() (y 1)) m.end()) { m[x * grid[0].size() (y 1)] m[id] 1; new_ids.insert(x * grid[0].size() (y 1)); } } ids new_ids; } } };其他应用A算法CSU 1588 合并果子CCF-CSP-2017-3-4 地铁修建力扣 347. 前 K 个高频元素力扣 373. 查找和最小的K对数字力扣 378. 有序矩阵中第K小的元素力扣 1090. 受标签影响的最大值力扣 1631. 最小体力消耗路径力扣 451. 根据字符出现频率排序2020编码大赛2初赛 
长河君 · 2026/9/7 11:07:23 · 阅读 1.2k 优先队列(priority queue)
目录一优先队列二STL优先队列三二叉堆实现优先队列四二项堆实现优先队列五线段树实现优先队列六OJ实战力扣 295. 数据流的中位数力扣 LCP 24. 数字游戏力扣 LCP 30. 魔塔游戏力扣 2462. 雇佣 K 位工人的总代价力扣 632. 最小区间力扣 857. 雇佣 K 名工人的最低成本力扣 1705. 吃苹果的最大数目其他应用一优先队列优先队列可以插入元素、查询最大值、删除最大值。优先队列其实就是最大堆或最小堆最大堆可以用来实现最大优先队列最小堆可以用来实现最小优先队列。用各种堆都可以实现优先队列。二STL优先队列优先队列如果要自定义排序函数只能用仿函数不能用普通函数的指针。示例#includeiostream #includequeue #includefunctional using namespace std; class cmp { public: bool operator()(int a, int b) { return a b; } }; bool cmp2(int a, int b) { return a b; } template typename A void display() { A q; q.push(1); q.push(3); q.push(4); q.push(2); while (!q.empty()) { cout q.top(); q.pop(); } cout endl; } int main() { display priority_queueint, vectorint (); //默认大顶堆 display priority_queue int, vectorint, greaterint ();//小顶堆 display priority_queue int, vectorint, lessint ();//大顶堆 display priority_queueint, vectorint, cmp();//大顶堆 //display priority_queueint, vectorint, cmp2(); 错误 return 0; }输出4321123443214321附上priority_queue的实现代码// TEMPLATE CLASS priority_queue templateclass _Ty, class _Container vector_Ty, class _Pr lesstypename _Container::value_type class priority_queue { // priority queue implemented with a _Container public: ...... 一堆函数 ...... protected: _Container c; // the underlying container _Pr comp; // the comparator functor };可以看出模板参数_Pr的默认值是less也就是说默认排序函数是less函数。priority_queue中包含一个排序的序列堆顶是这个序列的最后一个元素所以从小到大排序是大顶堆从大到小排序是小顶堆。三二叉堆实现优先队列二叉堆最大优先队列#includeiostream #include vector using namespace std; templatetypename T bool cmp(T a, T b) { return a b; //最大堆 } templatetypename T void exchange(T* a, T* b) { T tmp *a; *a *b; *b tmp; } int LeftChild(int id) { return id * 2; } int RightChild(int id) { return id * 2 1; } int Parent(int id) { return id/2; } templatetypename T void AdjustHeap(T* arr, int rootId, int size) { int largest rootId, left LeftChild(rootId), right RightChild(rootId); if (left size cmp(arr[largest], arr[left]))largest left; if (right size cmp(arr[largest], arr[right]))largest right; if (largest rootId)return; exchange(arr rootId, arr largest); AdjustHeap(arr, largest, size); } templatetypename T void HeapIncrese(T* arr, int size, int id, T newValue) { arr[id] newValue; while (id 0 cmp(arr[Parent(id)], arr[id])) { exchange(arr id, arr Parent(id)); id Parent(id); } } templatetypename T void HeapInsert(T* arr, int size,T value) { HeapIncrese(arr,size1,size,value); size; } int g_size; void Init() { g_size 0; } templatetypename T T Top(T* arr) { return arr[0]; } templatetypename T void Push(T* arr, T value) { HeapInsert(arr,g_size,value); } templatetypename T void Pop(T* arr) { g_size--; exchange(arr, arrg_size); AdjustHeap(arr, 0, g_size); } int main() { int q[10]; Init(); Push(q,4); Push(q,2); Push(q,6); Push(q,3); Push(q,4); Push(q,5); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutTop(q) ; Pop(q); coutendlg_size; return 0; }运行结果6 5 4 4 3 20四二项堆实现优先队列二项堆 里面已经实现了push、pop、top等操作所以它就是一种优先队列。五线段树实现优先队列代码struct anode { int t; int d; }; int n; int num[10001],maxx[40001]; struct anode node[10001]; void build(int key, int low, int high)//id { if (low high) { maxx[key] low; return; } int mid (low high) / 2; build(key * 2, low, mid); build(key * 2 1, mid 1, high); maxx[key] (num[maxx[key * 2]] num[maxx[key * 2 1]]) ? maxx[key * 2] : maxx[key * 2 1]; } void update(int key, int low, int high, int uplace)//id { if (low high) { maxx[key] low; return; } int mid (low high) / 2; if (uplace mid)update(key * 2, low, mid, uplace); else update(key * 2 1, mid 1, high, uplace); maxx[key] (num[maxx[key * 2]] num[maxx[key * 2 1]]) ? maxx[key * 2] : maxx[key * 2 1]; } int query(int key, int low, int high, int x, int y)//id { if (low x high y)return maxx[key]; int mid (low high) / 2; if (mid x)return query(key * 2 1, mid 1, high, x, y); if (mid y)return query(key * 2, low, mid, x, y); int a query(key * 2, low, mid, x, mid); int b query(key * 2 1, mid 1, high, mid 1, y); return (num[a]num[b]) ? a : b; } void push(int loc) { num[loc]node[loc].t; ///根据实际情况修改 update(1,1,n,loc); } void pop(int loc) { num[loc]0; ///根据实际情况修改 update(1,1,n,loc); } int top()//id { return query(1,1,n,1,n); }应用力扣 630. 课程表 III六OJ实战力扣 295. 数据流的中位数中位数是有序列表中间的数。如果列表长度是偶数中位数则是中间两个数的平均值。例如[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 3) / 2 2.5设计一个支持以下两种操作的数据结构void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。示例addNum(1)addNum(2)findMedian() - 1.5addNum(3)findMedian() - 2思路维护1个最大堆和1个最小堆并动态维持他们的尺寸相同。class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty()||numqmax.top())qmax.push(num); else qmin.push(num); } double findMedian() { while (qmin.size() qmax.size()) qmax.push(qmin.top()),qmin.pop(); while (qmax.size() qmin.size()1)qmin.push(qmax.top()),qmax.pop(); if (qmax.size() qmin.size())return qmax.top(); return (qmax.top() qmin.top()) / 2.0; } private: priority_queueint, vectorint qmax; priority_queue int, vectorint, greaterint qmin; };或者用自己实现的堆templatetypename T class MyHeap { public: T arr[100000]; MyHeap(int type)//0最小堆1最大堆 { this-type type; } T Top() { return arr[0]; } void Push(T value) { HeapInsert(arr, value); } void Pop() { size--; exchange(arr, arr size); AdjustHeap(arr, 0); } bool empty() { return size 0; } int Size() { return size; } private: void AdjustHeap(T* arr, int rootId) { int largest rootId, left LeftChild(rootId), right RightChild(rootId); if (left size cmp(arr[largest], arr[left]))largest left; if (right size cmp(arr[largest], arr[right]))largest right; if (largest rootId)return; exchange(arr rootId, arr largest); AdjustHeap(arr, largest); } void HeapIncrese(T* arr, int id, T newValue) { arr[id] newValue; while (id 0 cmp(arr[Parent(id)], arr[id])) { exchange(arr id, arr Parent(id)); id Parent(id); } } void HeapDecrese(T* arr, int size, int id, T newValue) { arr[id] newValue; AdjustHeap(arr, id, size); } void HeapChange(T* arr, int id, T newValue) { if (cmp(arr[id], newValue))HeapIncrese(arr, id, newValue); else HeapDecrese(arr, id, newValue); } void HeapInsert(T* arr, T value) { HeapIncrese(arr, size, value); } bool cmp(T a, T b) { return type ? (a b) : (a b); } void exchange(T* a, T* b) { T tmp *a; *a *b; *b tmp; } int LeftChild(int id) { return id * 2 1; } int RightChild(int id) { return id * 2 2; } int Parent(int id) { return (id - 1) / 2; } int type; int size 0; }; class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty() || num qmax.Top())qmax.Push(num); else qmin.Push(num); } double findMedian() { while (qmin.Size() qmax.Size()) qmax.Push(qmin.Top()), qmin.Pop(); while (qmax.Size() qmin.Size() 1)qmin.Push(qmax.Top()), qmax.Pop(); if (qmax.Size() qmin.Size())return qmax.Top(); return (qmax.Top() qmin.Top()) / 2.0; } private: MyHeapint qmax{ 1 }; MyHeapint qmin{ 0 }; };力扣 LCP 24. 数字游戏小扣在秋日市集入口处发现了一个数字游戏。主办方共有N个计数器计数器编号为0 ~ N-1。每个计数器上分别显示了一个数字小扣按计数器编号升序将所显示的数字记于数组nums。每个计数器上有两个按钮分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器按下加一或减一按钮。主办方请小扣回答出一个长度为N的数组第i个元素(0 i N)表示将0~i号计数器初始所示数字操作成满足所有条件nums[a]1 nums[a1],(0 a i)的最小操作数。回答正确方可进入秋日市集。由于答案可能很大请将每个最小操作数对1,000,000,007取余。示例 1输入nums [3,4,5,1,6,7]输出[0,0,0,5,6,7]解释 i 0[3] 无需操作 i 1[3,4] 无需操作 i 2[3,4,5] 无需操作 i 3将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作 i 4将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作 i 5将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]最少 7 次操作 返回 [0,0,0,5,6,7]。示例 2输入nums [1,2,3,4,5]输出[0,0,0,0,0]解释对于任意计数器编号 i 都无需操作。示例 3输入nums [1,1,1,2,3,4]输出[0,1,2,3,3,3]解释 i 0无需操作 i 1将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作 i 2将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]最少 2 次操作 i 3将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]最少 3 次操作 i 4将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]最少 3 次操作 i 5将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]最少 3 次操作 返回 [0,1,2,3,3,3]。提示1 nums.length 10^51 nums[i] 10^3思路把力扣 295. 数据流的中位数中的MedianFinder进行改造数据流的形式不变把查询中位数改成查询所有数到中位数的距离总和。实现的思路不变时间复杂度也不变。利用改造后的MedianFinder直接可以得到本题的答案。class MedianFinder { public: MedianFinder() { } void addNum(int num) { if (qmax.empty() || num qmax.top()) { if (qmax.size() qmin.size()) { qmax.push(num); s qmax.top() - num; } else { qmin.push(qmax.top()), qmax.pop(); qmax.push(num); s qmin.top() - num; } } else { if (qmax.size() qmin.size()) { qmin.push(num); s num - qmin.top(); qmax.push(qmin.top()), qmin.pop(); } else { qmin.push(num); s num - qmax.top(); } } } long long sumLen() { return s; } private: long long s 0; priority_queueint, vectorint qmax;//最大堆放小的一半数据 priority_queue int, vectorint, greaterint qmin;//最小堆放大的一半数据 }; class Solution { public: vectorint numsGame(vectorint nums) { MedianFinder opt; vectorintans; for(int i0;inums.size();i){ opt.addNum(nums[i]-i); ans.push_back(opt.sumLen() % 1000000007); } return ans; } };力扣 LCP 30. 魔塔游戏小扣当前位于魔塔游戏第一层共有N个房间编号为0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组nums其中正数表示道具补血数值即血量增加对应数值负数表示怪物造成伤害值即血量减少对应数值0表示房间对血量无影响。小扣初始血量为 1且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪为保证血量始终为正值小扣需对房间访问顺序进行调整每次仅能将一个怪物房间负数的房间调整至访问顺序末尾。请返回小扣最少需要调整几次才能顺利访问所有房间。若调整顺序也无法访问完全部房间请返回 -1。示例 1输入nums [100,100,100,-250,-60,-140,-50,-50,100,150]输出1解释初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。示例 2输入nums [-200,-300,400,0]输出-1解释调整访问顺序也无法完成全部房间的访问。提示1 nums.length 10^5-10^5 nums[i] 10^5class Solution { public: int magicTower(vectorint nums) { priority_queueint, vectorintq; long long s 0, s2 0, n 0; for (auto x : nums) { if (x 0)q.push(-x); s x; if (s 0) { s q.top(); s2 q.top(); q.pop(); n; } } if (s - s2 0)return n; return -1; } };力扣 2462. 雇佣 K 位工人的总代价给你一个下标从0开始的整数数组costs其中costs[i]是雇佣第i位工人的代价。同时给你两个整数k和candidates。我们想根据以下规则恰好雇佣k位工人总共进行k轮雇佣且每一轮恰好雇佣一位工人。在每一轮雇佣中从最前面candidates和最后面candidates人中选出代价最小的一位工人如果有多位代价相同且最小的工人选择下标更小的一位工人。比方说costs [3,2,7,7,1,2]且candidates 2第一轮雇佣中我们选择第4位工人因为他的代价最小[3,2,7,7,1,2]。第二轮雇佣我们选择第1位工人因为他们的代价与第4位工人一样都是最小代价而且下标更小[3,2,7,7,2]。注意每一轮雇佣后剩余工人的下标可能会发生变化。如果剩余员工数目不足candidates人那么下一轮雇佣他们中代价最小的一人如果有多位代价相同且最小的工人选择下标更小的一位工人。一位工人只能被选择一次。返回雇佣恰好k位工人的总代价。示例 1输入costs [17,12,10,2,7,2,11,20,8], k 3, candidates 4输出11解释我们总共雇佣 3 位工人。总代价一开始为 0 。 - 第一轮雇佣我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 有两位工人我们选择下标更小的一位工人即第 3 位工人。总代价是 0 2 2 。 - 第二轮雇佣我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 下标为 4 总代价是 2 2 4 。 - 第三轮雇佣我们从 [17,12,10,7,11,20,8] 中选择最小代价是 7 下标为 3 总代价是 4 7 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。 总雇佣代价是 11 。示例 2输入costs [1,2,4,1], k 3, candidates 3输出4解释我们总共雇佣 3 位工人。总代价一开始为 0 。 - 第一轮雇佣我们从 [1,2,4,1] 中选择。最小代价为 1 有两位工人我们选择下标更小的一位工人即第 0 位工人总代价是 0 1 1 。注意下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。 - 第二轮雇佣我们从 [2,4,1] 中选择。最小代价为 1 下标为 2 总代价是 1 1 2 。 - 第三轮雇佣少于 3 位工人我们从剩余工人 [2,4] 中选择。最小代价是 2 下标为 0 。总代价为 2 2 4 。 总雇佣代价是 4 。提示1 costs.length 1051 costs[i] 1051 k, candidates costs.lengthstruct Node { int x, id; }; class cmp { public: bool operator()(Node a, Node b) { if (a.x b.x)return a.id b.id; return a.x b.x; } }; class Solution { public: long long totalCost(vectorint costs, int k, int candidates) { priority_queueNode, vectorNode, cmpq; int low 0, high costs.size() - 1; while (low candidates low costs.size()) { q.push(Node{ costs[low],low }); } while (high costs.size() - candidates high low) { q.push(Node{ costs[high],high-- }); } long long ans 0; while (!q.empty() k--) { Node nod q.top(); q.pop(); ans nod.x; if (low high) { if(nod.idlow)q.push(Node{ costs[low],low }); else q.push(Node{ costs[high],high-- }); } } return ans; } };力扣 632. 最小区间你有k个非递减排列的整数列表。找到一个最小区间使得k个列表中的每个列表至少有一个数包含在其中。我们定义如果b-a d-c或者在b-a d-c时a c则区间[a,b]比[c,d]小。示例 1输入nums [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]输出[20,24]解释列表 1[4, 10, 15, 24, 26]24 在区间 [20,24] 中。 列表 2[0, 9, 12, 20]20 在区间 [20,24] 中。 列表 3[5, 18, 22, 30]22 在区间 [20,24] 中。示例 2输入nums [[1,2,3],[1,2,3],[1,2,3]]输出[1,1]提示nums.length k1 k 35001 nums[i].length 50-105 nums[i][j] 105nums[i]按非递减顺序排列struct Node { int x, id; }; class cmp { public: bool operator()(Node a, Node b) { return a.x b.x; } }; class Solution { public: vectorint smallestRange(vectorvectorint nums) { vectorintids(nums.size(), 0); vectorintans{-100000,100000}; priority_queueNode, vectorNode, cmpq;//最小堆 int minMax 100000; int maxid 0; for (int i 0; i ids.size(); i) { if (nums[i][0] nums[maxid][0])maxid i; minMax min(minMax, nums[i][nums[i].size() - 1]); q.push(Node{ nums[i][0],i }); } while (true) { int t q.top().x; int minid q.top().id; q.pop(); if (ans[1] - ans[0] nums[maxid][ids[maxid]] - nums[minid][ids[minid]] || (ans[1] - ans[0] nums[maxid][ids[maxid]] - nums[minid][ids[minid]] ans[0] nums[minid][ids[minid]])) { ans vectorint{ nums[minid][ids[minid]] ,nums[maxid][ids[maxid]] }; } if (ids[minid] 1 nums[minid].size())return ans; ids[minid]; if (nums[minid][ids[minid]] nums[maxid][ids[maxid]])maxid minid; q.push(Node{ nums[minid][ids[minid]],minid }); } return ans; } };力扣 857. 雇佣 K 名工人的最低成本有n名工人。 给定两个数组quality和wage其中quality[i]表示第i名工人的工作质量其最低期望工资为wage[i]。现在我们想雇佣k名工人组成一个工资组。在雇佣 一组k名工人时我们必须按照下述规则向他们支付工资对工资组中的每名工人应当按其工作质量与同组其他工人的工作质量的比例来支付工资。工资组中的每名工人至少应当得到他们的最低期望工资。给定整数k返回组成满足上述条件的付费群体所需的最小金额。在实际答案的10-5以内的答案将被接受。。示例 1输入quality [10,20,5], wage [70,50,30], k 2输出105.00000解释我们向 0 号工人支付 70向 2 号工人支付 35。示例 2输入quality [3,1,10,10,1], wage [4,8,2,2,7], k 3输出30.66667解释我们向 0 号工人支付 4向 2 号和 3 号分别支付 13.33333。提示n quality.length wage.length1 k n 1041 quality[i], wage[i] 104struct Node { int q, w; }; bool cmp(Node a, Node b) { return a.w * b.q b.w * a.q; } class cmp2 { public: bool operator()(Node a, Node b) { return a.q b.q; } }; class Solution { public: double mincostToHireWorkers(vectorint quality, vectorint wage, int k) { vectorNodev; for (int i 0; i quality.size(); i) { v.push_back(Node{ quality[i],wage[i] }); } sort(v.begin(), v.end(), cmp); priority_queueNode, vectorNode, cmp2q; int s 0; for (int i 0; i k; i) { s v[i].q; q.push(v[i]); } double ans v[k - 1].w * 1.0 / v[k - 1].q * s; for (int i k; i v.size(); i) { s v[i].q; q.push(v[i]); auto nod q.top(); q.pop(); s - nod.q; ans min(ans, v[i].w * 1.0 / v[i].q * s); } return ans; } };力扣 1705. 吃苹果的最大数目有一棵特殊的苹果树一连n天每天都可以长出若干个苹果。在第i天树上会长出apples[i]个苹果这些苹果将会在days[i]天后也就是说第i days[i]天时腐烂变得无法食用。也可能有那么几天树上不会长出新的苹果此时用apples[i] 0且days[i] 0表示。你打算每天最多吃一个苹果来保证营养均衡。注意你可以在这n天之后继续吃苹果。给你两个长度为n的整数数组days和apples返回你可以吃掉的苹果的最大数目。示例 1输入apples [1,2,3,5,2], days [3,2,1,4,2]输出7解释你可以吃掉 7 个苹果 - 第一天你吃掉第一天长出来的苹果。 - 第二天你吃掉一个第二天长出来的苹果。 - 第三天你吃掉一个第二天长出来的苹果。过了这一天第三天长出来的苹果就已经腐烂了。 - 第四天到第七天你吃的都是第四天长出来的苹果。示例 2输入apples [3,0,0,0,0,2], days [3,0,0,0,0,2]输出5解释你可以吃掉 5 个苹果 - 第一天到第三天你吃的都是第一天长出来的苹果。 - 第四天和第五天不吃苹果。 - 第六天和第七天你吃的都是第六天长出来的苹果。提示apples.length ndays.length n1 n 2 * 1040 apples[i], days[i] 2 * 104只有在apples[i] 0时days[i] 0才成立思路直接按照deadline排序做成小顶堆struct Node { int num; int deadline; bool operator(const Node nod)const { return deadline nod.deadline; } }; class Solution { public: int eatenApples(vectorint apples, vectorint days) { priority_queueNode, vectorNode, greaterNodeq; int ans 0; for (int i 0; i days.size() || !q.empty(); i) { if (i days.size() days[i]0) { q.push(Node{ apples[i],days[i] i - 1 }); } while (!q.empty()) { Node nod q.top(); q.pop(); if (nod.deadline i) continue; if (--nod.num 0 nod.deadline i) { q.push(nod); } ans; break; } } return ans; } };力扣 2812. 找出最安全路径给你一个下标从0开始、大小为n x n的二维矩阵grid其中(r, c)表示如果grid[r][c] 1则表示一个存在小偷的单元格如果grid[r][c] 0则表示一个空单元格你最开始位于单元格(0, 0)。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。矩阵中路径的安全系数定义为从路径中任一单元格到矩阵中任一小偷所在单元格的最小曼哈顿距离。返回所有通向单元格(n - 1, n - 1)的路径中的最大安全系数。单元格(r, c)的某个相邻单元格是指在矩阵中存在的(r, c 1)、(r, c - 1)、(r 1, c)和(r - 1, c)之一。两个单元格(a, b)和(x, y)之间的曼哈顿距离等于| a - x | | b - y |其中|val|表示val的绝对值。示例 1输入grid [[1,0,0],[0,0,0],[0,0,1]]输出0解释从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。示例 2输入grid [[0,0,1],[0,0,0],[0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格02最近的单元格是00。它们之间的曼哈顿距离为 | 0 - 0 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。示例 3输入grid [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格03最近的单元格是12。它们之间的曼哈顿距离为 | 0 - 1 | | 3 - 2 | 2 。 - 该路径上距离小偷所在单元格30最近的单元格是32。它们之间的曼哈顿距离为 | 3 - 3 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。提示1 grid.length n 400grid[i].length ngrid[i][j]为0或1grid至少存在一个小偷class Solution { public: int maximumSafenessFactor(vectorvectorint grid) { mapint, intm; setintids; for (int i 0; i grid.size(); i) { for (int j 0; j grid[0].size(); j) { if (grid[i][j] 1) { m[i * grid[0].size() j] 1; ids.insert(i * grid[0].size() j); } } } bfs(ids, grid, m); auto v grid; for (int i 0; i grid.size(); i) { for (int j 0; j grid[0].size(); j) { v[i][j] m[i * grid[0].size() j]; } } return maximumMinimumPath(v)-1; } int maximumMinimumPath(vectorvectorint grid) { int m grid.size(); if (m 0) return 0; int n grid[0].size(); if (n 0) return 0; // 大顶堆优先队列存储 {路径最小值, 行, 列} // C priority_queue 默认是最大堆 priority_queuepairint, pairint, int pq; // 记录节点是否被访问过 vectorvectorbool visited(m, vectorbool(n, false)); // 起点入队 pq.push({ grid[0][0], {0, 0} }); visited[0][0] true; // 上下左右四个方向 int dirs[4][2] { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; while (!pq.empty()) { auto curr pq.top(); pq.pop(); int val curr.first; // 当前路径上的最小值 int r curr.second.first; // 当前行 int c curr.second.second; // 当前列 // 如果已经到达右下角直接返回当前路径的最小值 if (r m - 1 c n - 1) { return val; } // 向四个方向扩展 for (int i 0; i 4; i) { int nr r dirs[i][0]; int nc c dirs[i][1]; // 检查边界和是否访问过 if (nr 0 nr m nc 0 nc n !visited[nr][nc]) { visited[nr][nc] true; // 扩展到邻居节点后路径的最小值为当前 val 和邻居节点值的较小者 int next_val min(val, grid[nr][nc]); pq.push({ next_val, {nr, nc} }); } } } return -1; // 理论上不会执行到这里 } void bfs(setintids, vectorvectorint grid, mapint, intm) { while (m.size() grid.size() * grid[0].size()) { setintnew_ids; for (auto id : ids) { int x id / grid[0].size(); int y id % grid[0].size(); if (x 0 m.find((x - 1) * grid[0].size() y) m.end()) { m[(x - 1) * grid[0].size() y] m[id] 1; new_ids.insert((x - 1) * grid[0].size() y); } if (x grid.size() - 1 m.find((x 1) * grid[0].size() y) m.end()) { m[(x 1) * grid[0].size() y] m[id] 1; new_ids.insert((x 1) * grid[0].size() y); } if (y 0 m.find(x * grid[0].size() (y - 1)) m.end()) { m[x * grid[0].size() (y - 1)] m[id] 1; new_ids.insert(x * grid[0].size() (y - 1)); } if (y grid[0].size() - 1 m.find(x * grid[0].size() (y 1)) m.end()) { m[x * grid[0].size() (y 1)] m[id] 1; new_ids.insert(x * grid[0].size() (y 1)); } } ids new_ids; } } };其他应用A算法CSU 1588 合并果子CCF-CSP-2017-3-4 地铁修建力扣 347. 前 K 个高频元素力扣 373. 查找和最小的K对数字力扣 378. 有序矩阵中第K小的元素力扣 1090. 受标签影响的最大值力扣 1631. 最小体力消耗路径力扣 451. 根据字符出现频率排序2020编码大赛2初赛